Stationary Points of a Shallow Neural Network with Quadratic Activations and the Global Optimality of the Gradient Descent Algorithm

1. Introduction

Neural network architectures are demonstrated to be extremely powerful in practical tasks, such as natural language processing (Collobert and Weston [20]), image recognition (He et al. [46]), image classification (Krizhevsky et al. [53]), speech recognition (Mohamed et al. [63]), and game playing (Silver et al. [80]), and is becoming popular in other areas, such as applied mathematics (Chen et al. [17], Weinan et al. [94]), clinical diagnosis (De Fauw et al. [21]), and so on. Despite this empirical success, a rigorous mathematical understanding of these architectures is still an ongoing quest.

Despite the fact that it is NP-hard to train such architectures in the worst case setting, it has been observed empirically that the gradient descent (GD), albeit a simple, first order, local procedure, is rather successful in training such networks. This is somewhat surprising because of the highly nonconvex nature of the associated objective function. Our main motivation in this paper is to provide further insights into the optimization landscape and generalization abilities of these networks.

1.1. Model, Contributions, and Comparison with Prior Work

In this section, we introduce the model considered in this paper, describe our contributions, and discuss the relevant literature.

1.1.1. Model.

In this paper, we consider a shallow neural network architecture with one hidden layer of width m. Namely, the network consists of m neurons. We study it under the realizable model assumption, that is, the labels are generated by a teacher network with ground truth weight matrix $W^{*}\in {\mathbb{R}}^{m\times d}$ whose $j\text{th}$ row $W_j^{*}\in {\mathbb{R}}^d$ carries the weights of the $j\text{th}$ neuron and $m\ge d$. We assume that the input data $X\in {\mathbb{R}}^d$ consists of independent and identically distributed (i.i.d.) centered sub-Gaussian coordinates. It is worth noting that such shallow architectures with planted weights and Gaussian input data are explored extensively in the literature (see, e.g., Brutzkus and Globerson [11], Du et al. [28], Li and Yuan [56], Soltanolkotabi [82], Tian [89], Zhong et al. [99]).

Our focus is, in particular, on networks with quadratic activation, studied also by Soltanolkotabi et al. [83] and Du and Lee [24], among others. This object, an instance of what is known as a polynomial network (Livni et al. [59]), computes for every input data $X\in {\mathbb{R}}^d$ the function

We note that, albeit a stylized activation function, blocks of quadratic activations can be stacked together to approximate deeper networks with sigmoid activations as shown by Livni et al. [59], and furthermore, this activation serves as a second order approximation of general nonlinear activations as noted by Venturi et al. [90]. Thus, we study the quadratic networks as an attempt to gain further insights on more complex networks.

Let $X_i\in {\mathbb{R}}^d,\hspace{0.17em}1\le i\le N$ be an i.i.d. collection of input data, and let $Y_i=f(W^{*};X_i)$ be the corresponding label generated per (1). The goal of the learner is as follows: given the training data $(X_i,Y_i)\in {\mathbb{R}}^d\times \mathbb{R},\hspace{0.17em}1\le i\le N$, find a weight matrix $W\in {\mathbb{R}}^{m\times d}$ that explains the input–output relationship on the training data set in the best possible way, often by solving the so-called empirical risk minimization (ERM) optimization problem

understand its generalization ability, quantified by the generalization error (also known as the population risk associated with any solution candidate $W\in {\mathbb{R}}^{m\times d}$) that is given bywhere the expectation is with respect to a fresh sample X, which has the same distribution as $X_i,1\le i\le N$ but is independent from the sample. The landscape of the loss function $\widehat{\mathcal{L}}(·)$ is nonconvex, therefore rendering the optimization problem (potentially) difficult. Nevertheless, the gradient descent algorithm, despite being a simple first order procedure, is rather successful in training neural networks in general: it appears to find a $W\in {\mathbb{R}}^{m\times d}$ with near-optimal $\widehat{\mathcal{L}}(W).$ Our partial motivation is to investigate this phenomenon in the case in which the activation function is quadratic.

1.1.2. Contributions.

We first study the landscape of risk functions and quantify an energy barrier separating rank-deficient matrices from the full-rank planted weights. Specifically, if $W^{*}\in {\mathbb{R}}^{m\times d}$ is full-rank, namely, rank d (recall $m\ge d$), then the risk function for any rank-deficient W is bounded away from zero by an explicit constant—independent of d—controlled by the smallest singular value ${\sigma }_{\text{min}}(W^{*})$ of $W^{*}$ as well as the second and fourth moments of the data. See Theorem 1 for the population and Theorem 2 for the empirical versions of this result. (Theorem 2 holds with high probability (w.h.p.) with respect to the observed sample.)

Next, we study the full-rank stationary points of the risk functions and the performance of the gradient descent algorithm. We first establish that, when $W^{*}$ is full rank, any full-rank stationary point W of the risk functions is necessarily a global minimum and any such W is of form $W=Q{W}^{*}$, where $Q\in {\mathbb{R}}^{m\times m}$ is orthonormal. See Theorem 3 for the population and Theorem 4 for the empirical versions. Namely, W is a global optimum up to a rotation. We then establish that all approximate stationary points (appropriately defined) W of $\widehat{\mathcal{L}}(·)$ below the aforementioned energy barrier are nearly global optimum. Furthermore, we establish that, if the number N of samples is $\text{poly}(d)$, then the weights W of any full-rank approximate stationary point are uniformly close to $W^{*}$. As a corollary, gradient descent with initialization below the energy barrier recovers in time $\text{poly}({ϵ}^{-1},d)$ a solution W for which the weights are ϵ-close to the planted weights. Consequently, the generalization error $\mathcal{L}(W)$ for this solution W is at most ϵ. The bound on $\mathcal{L}(W)$ is derived by controlling the condition number of a certain matrix whose i.i.d. rows consists of tensorized data $X_i^{\otimes 2}$, using a recently developed machinery in Emschwiller et al. [33] studying the spectrum of expected covariance matrices of tensorized data. See Theorem 5 for the population and Theorem 6 for the empirical version.

Subsequently, we study the question of whether one can find the initialization of the gradient descent algorithm below the aforementioned energy barrier. We answer affirmatively this question in the context of randomly generated $W^{*}\in {\mathbb{R}}^{m\times d}$ and establish in Theorem 8 that, as long as the network is sufficiently overparameterized, specifically $m>C{d}^2$, for some sufficiently large constant C, it is possible to initialize W₀ such that w.h.p. the risk associated to W₀ is below the required threshold. This is achieved by using tools from random matrix theory, specifically a semicircle law for Wishart matrices that shows the spectrum of ${(W^{*})}^T{W}^{*}$ is tightly concentrated (Bai and Yin [3]). See Theorem 7 for the population and Theorem 8 for the empirical version. It is worth noting that neural networks with random weights is an active area of research by itself because of the relationship with random feature methods. For example, Rahimi and Recht [73] show that shallow architectures trained by choosing the internal weights randomly and optimizing only over the output weights return a classifier with reasonable generalization performance at accelerated training speed. Random shallow networks are also shown to well-approximate dynamical systems (Gonon et al. [40]), have been successfully employed in the context of extreme learning machines (Huang et al. [48]), and are studied in the context of random matrix theory; see Pennington and Worah [69] and references therein.

Our next focus is on the sample complexity for generalization. Even though we study the landscape of the empirical risk, it is not by any means certain that any (potentially not full-rank) optimizer of ${\min }_W \widehat{\mathcal{L}}(W)$ also achieves zero generalization error. We give necessary and sufficient conditions on the samples $X_i,1\le i\le N$ so that any minimizer has indeed zero generalization error in our setting. We show that, if $\text{span}(X_i{X}_i^T:1\le i\le N)$ is the space of all d × d-dimensional real symmetric matrices, then any global minimum of the empirical risk is necessarily a global optimizer of the population risk and, thus, has zero generalization error. Note that this geometric condition is not retrospective in manner: it can be checked ahead of the optimization procedure by computing $\text{span}(X_i{X}_i^T:1\le i\le N)$. Conversely, we show that, if the preceding span condition is not met, then there exists a global minimum W of the empirical risk function that induces a strictly positive generalization error. This is established in Theorem 9.

To complement our analysis, we then ask the following question: what is the critical number $N^{*}$ of the training samples under which the (random) data $X_i,1\le i\le N$ enjoys the aforementioned span condition? We prove this number to be $N^{*}=d(d+1)/2$ under a very mild assumption that the coordinates of $X_i\in {\mathbb{R}}^d$ are jointly continuous. This is shown in Theorem 10. Finally in Theorem 11, we show that, when $N<N^{*}$, not only does there exist W with zero empirical risk and strictly positive generalization error, we also bound this error from below by an amount very similar to the bound for rank-deficient matrices discussed in our earlier Theorem 2.

We end with a comment on overparameterization and generalization. A common paradigm in statistical learning theory is that overparameterized models, that is, models with more parameters than necessary, although capable of interpolating the training data, tend to generalize poorly because of overfitting to the proposed model. Yet it is observed empirically that neural networks tend not to suffer from this complication (Zhang et al. [96]): despite being overparameterized, they seem to have a good generalization performance provided the interpolation barrier is exceeded. In Theorem 9(a), we establish the following result, which sheds some light on this phenomenon for the case of shallow neural networks with quadratic activations: suppose that the data enjoys the aforementioned geometric condition. Then, any interpolator achieves zero generalization error even when the interpolator is a neural network with a potentially larger number $\widehat{m}$ of internal nodes compared with the one that generated the data, namely, by using a weight matrix $W\in {\mathbb{R}}^{\widehat{m}\times d}$, where $\widehat{m}\ge m$. In other words, the model does not overfit when a much larger width of the interpolator is chosen at the learning state.

1.1.3. Comparison with Soltanolkotabi et al. [83] and Du and Lee [24].

We now make a comparison with two very related prior works, also studying quadratic activations. We start with the work by Soltanolkotabi et al. [83]. In Soltanolkotabi et al. [83, theorem 2.2], the authors study the empirical risk landscape of a slightly more general version of our model: $Y_i={\sum }_{j=1}^m{v}_j^{*}{〈W_j^{*},X_i〉}^2$, assuming $\text{rank}(W^{*})=d$ like us and assuming all nonzero entries of $v^{*}$ have the same sign. Thus, our model is the special case in which all entries of $v^{*}$ are equal to unity. The authors establish that, as long as $d\le N\le c{d}^2$ for some small fixed constant c, every local minima of the empirical risk function is also a global minima (namely, there exists no spurious local minima), and furthermore, every saddle point has a direction of negative curvature. As a result, they show that gradient descent with an arbitrary initialization converges to a globally optimum solution of the ERM problem (2). In particular, their result does not require the initialization point to be below some risk value (the energy barrier) as in our case. Nevertheless, our results show that one needs not to worry about saddle points below the energy barrier as none exists per our Theorem 2. Importantly, though, the regime $N<c{d}^2$ for small c that Soltanolkotabi et al. [83, theorem 2.2] applies is below the provable sample complexity value $N^{*}=d(d+1)/2$ when the data are drawn from a continuous distribution as per our Theorem 10. In particular, as we establish when $N<N^{*}$, the ERM problem (2) admits global optimum solutions with zero empirical risk value but with the generalization error bounded away from zero. Thus, the regime $N<N^{*}$ does not correspond to the regime in which solving the ERM has a guaranteed control on the generalization error. The same theorem in Soltanolkotabi et al. [83] also studies the approximate stationary points and shows that, for any such point W, the associated empirical risk, $\widehat{\mathcal{L}}(W)$, is also small. Our Theorem 6, though, takes a step further and shows that not only is the empirical risk small, but the recovered W is close to planted weights $W^{*}$, and therefore, it has a small generalization error $\mathcal{L}(W)$ by explicitly bounding the generalization error from above.

It is also worth noting that, although not our focus in the present paper, Soltanolkotabi et al. [83, theorem 2.1] also studies the landscape of the empirical risk when a quadratic network model $X\mapsto {\sum }_{j=1}^m{v}_j^{*}{〈W_j^{*},X〉}^2$ is used for interpolating arbitrary input/label pairs $(X_i,Y_i)\in {\mathbb{R}}^d\times \mathbb{R},\hspace{0.17em}1\le i\le N$, that is, without making an assumption that the labels are generated according to a network with planted weights. They establish similar landscape results, namely, the absence of spurious local minima and the fact that every saddle point has a direction of negative curvature as long as the output weight $v^{*}$ has at least d positive and at least d negative entries (consequently, the width m has to be at least 2d). Even though this result does not assume any rank condition on W, the assumption on the minimum number of positive and minimum number of negative entries, such as the preceding one, is somewhat unnatural.

Yet another closely related work studying quadratic activations is the paper by Du and Lee [24], which focuses on the shallow architectures with all unity output weights as we do. This paper establishes that, for any smooth and convex loss $\mathcal{\ell }(·,·)$, the landscape of the regularized loss function $\frac{1}{N}{\sum }_{i=1}^N\mathcal{\ell }(f(W;X_i),Y_i)+\frac{\lambda }{2}{\Vert W\Vert }_F^2$ still admits aforementioned favorable geometric characteristics. Furthermore, as the learned weights are of bounded Frobenius norm thanks to the norm penalty ${\Vert W\Vert }_F^2$ imposed on the objective, they retain good generalization via Rademacher complexity considerations. Even though this work addresses the training and generalization error when the norm of W is controlled during training, it does not carry out approximate stationarity analysis as Soltanolkotabi et al. [83] and we do and does not study their associated loss/generalization as in our case. Even though they show that optimal solutions to the optimization problem incorporating bounded norms generalize well, it remains unclear from their analysis whether the approximate stationary points of this objective also have a well-controlled norm.

It is worth mentioning that the two main directions that we undertake in this paper were not explored in either of these two prior works. These include the direction pertaining to the initialization (Theorems 7 and 8) and the direction pertaining to the sample complexity (Theorems 9–11). The latter direction relates to an interesting interpolation/overparameterization property that we have discussed before. We return later to this direction in Section 2.3 after we present Theorem 9.

1.1.4. Connection to Matrix Sensing.

The problem of learning shallow quadratic networks with planted weights $W^{*}$ is closely related to the matrix sensing problem. This problem has many applications, spanning from video and image processing to control and sensor networks (see Deng et al. [23], Qin et al. [72], Zhong et al. [97] and references therein); we now elaborate on the connection between our setting and the matrix sensing problem. Given an unknown matrix $A^{*}\in {\mathbb{R}}^{d_1\times d_2}$, the goal of the matrix sensing problem is to recover $A^{*}$ from a (small) number of linear measurements of form $〈Z_i,A^{*}〉,\hspace{0.17em}1\le i\le N$, where $Z_i\in {\mathbb{R}}^{d_1\times d_2},\hspace{0.17em}1\le i\le N$, and $〈Z_i,A^{*}〉=\text{trace}(Z_i^T{A}^{*})$. Recalling (1), our data model corresponds to

Namely, the problem that we study in the present paper is an instance of the matrix sensing problem; the goal is to recover $A^{*}={(W^{*})}^T{W}^{*}$ from rank-1 measurements of form $X_i{X}_i^T$, where $X_i\in {\mathbb{R}}^d$ have centered i.i.d. sub-Gaussian coordinates. A related prior work by Zhong et al. [97] studies the problem of sensing a low-rank matrix from rank-1 measurements of form $X_i{Y}_i^T$, where $X_i,Y_i\in {\mathbb{R}}^d$ are i.i.d. and they consist of centered i.i.d. sub-Gaussian coordinates (see also Deng et al. [23] for an improvement of Zhong et al. [97] in terms of the time and sample complexity). Notice that Zhong et al. [97] studies a slightly different measurement matrix of form $X_i{Y}_i^T$ (as opposed to $X_i{X}_i^T$). More importantly Zhong et al. [97] are concerned with recovering a low-rank $A^{*}$, whereas the fact that ${(W^{*})}^T{W}^{*}$ is full-rank is crucial for our techniques; see subsequent details. A very recent work by Qin et al. [72] relaxes the low-rank assumption and studies measurement matrices of form $u_i{u}_i^T$ for $u_i\in {\mathbb{R}}^d$ that are nearly orthogonal and give recovery guarantees for the stochastic gradient descent. Note that, for $X_i\in {\mathbb{R}}^d$ as before, standard concentration arguments show that the collection X_i, $1\le i\le N$, consists (w.h.p.) of nearly orthogonal vectors. Therefore, the setting studied in Qin et al. [72] is very similar to ours, and their sample complexity guarantee regarding the gradient descent appears to have a better dependence on dimension than ours. On the other hand Qin et al. [72] focus only on the problem of finding an $\widehat{A}$ such that

is small; it is not clear from their analysis whether $\widehat{A}$ is also close to ground truth $A^{*}$, that is, whether $\Vert \widehat{A}-A^{*}\Vert$ is small. This is one of the main directions we explore in the present paper. For more on the matrix sensing problem, see Recht et al. [74], Zhong et al. [97], Deng et al. [23], Qin et al. [72], and the references therein.

1.1.5. Further Relevant Prior Work.

As noted in the introduction, neural networks achieved remarkable empirical success, which fueled research starting from the expressive ability of these networks, going as early as Barron [5]. More recent works along this front focus on deeper and sparser models; see, for example, Mhaskar et al. [62], Telgarsky [88], Eldan and Shamir [31], Schmidt-Hieber [78], Poggio et al. [70], and Bölcskei et al. [10]. In particular, the expressive power of such network architectures is relatively well understood. Another issue pertaining to such architectures is their computational tractability: Blum and Rivest [9] establish that it is NP-complete to train a very simple three-node network whose nodes compute a linear thresholding function. Despite this worst case result, it is observed empirically that local search algorithms, such as GD, are rather successful in training. Even though several authors, including Sedghi and Anandkumar [79], Janzamin et al. [49], and Goel et al. [38], devise provable training algorithms for such networks, these algorithms unfortunately are based on methods other than the gradient descent, thus not shedding any light on its apparent empirical success.

On a parallel front, many papers study the behavior of the GD by analyzing the trajectory of it or its stochastic variant (SGD) under certain stylistic assumptions on the data as well as the network. These assumptions include Gaussian inputs, shallow networks (with or without the convolutional structure), and the existence of planted weights (the so-called teacher network) generating the labels. Some partial and certainly very incomplete references to this end include Tian [89], Brutzkus and Globerson [11], Brutzkus et al. [12], Zhong et al. [98], Soltanolkotabi [82], Li and Yuan [56], and Du et al. [28]. Later work relaxes the distributional assumptions. For instance, Du et al. [25] study the problem of learning a convolutional unit with ReLU with no specific distributional assumption on input and establish the convergence of SGD with rate depending on the smoothness of the input distribution and the closeness of the patches. Several other works along this line, in particular under the presence of overparameterization, are the works by Du et al. [26, 27].

Yet another line of research on the optimization front, rather than analyzing the trajectory of the GD, focuses on the mean-field analysis. Empirical distribution of the parameters of network with infinitely many internal nodes can be described as a Wasserstein gradient flow, and thus, some tools from the theory of optimal transport can be used; see, for example, Wei et al. [93], Rotskoff and Vanden-Eijnden [75], Chizat and Bach [18], Song et al. [84], and Sirignano and Spiliopoulos [81]. Albeit explaining the story to some extent for infinitely wide networks, it remains unclear whether these techniques provide results for a more realistic network model with finitely many internal nodes.

As noted earlier, the optimization landscape of such networks is usually highly nonconvex. More recent research on such nonconvex objectives shows that, if the landscape has certain favorable geometric properties, such as the absence of spurious local minima and the existence of direction with negative curvature for every saddle point, local methods can escape the saddle points and converge to the global minima. Examples of this line of research on loss functions include Ge et al. [37], Levy [55], Lee et al. [54], Jin et al. [50], and Du et al. [29]. Motivated by this front of research, many papers analyze geometric properties of the optimization landscape, including Poston et al. [71], Haeffele et al. [43], Choromanska et al. [19], Haeffele and Vidal [42], Kawaguchi [51], Hardt and Ma [44], Soudry and Carmon [85], Freeman and Bruna [34], Zhou and Feng [100], Nguyen and Hein [67, 68], Ge et al. [36], Safran and Shamir [77], Soudry and Hoffer [86], Zhou and Liang [101], Venturi et al. [90], Du et al. [24], and Soltanolkotabi et al. [83].

We now touch upon yet another very important focus, that is, the generalization ability of such networks: how well a solution found, for example, by GD, predicts unseen data? A common paradigm in statistical learning theory that was mentioned previously is that overparameterized models tend to generalize poorly. Yet neural networks tend to not suffer from this complication (Zhang et al. [96]). Because the Vapnik–Chervonenkis dimension of these networks grows (at least) linear in the number of parameters (Bartlett et al. [7], Harvey et al. [45]), standard Vapnik–Chervonenkis theory does not help explaining the good generalization ability under presence of overparameterization. This is studied, among others, through the lens of the norm of weight matrices (Bartlett et al. [6], Dziugaite and Roy [30], Golowich et al. [39], Liang et al. [58], Neyshabur et al. [65], Wu et al. [95]), PAC-Bayes theory (Neyshabur et al. [64, 66]), and compression-based bounds (Arora et al. [1]). A main drawback is that these papers require some sort of constraints on the weights and are mostly a posteriori: whether a good generalization takes place can be determined only when the training process is finished. A recent work by Arora et al. [2] provides an a priori guarantee for the solution found by the GD. Our result regarding the generalization guarantee described in Theorem 11 also provides simple a priori guarantee on the generalization.

1.1.6. A Follow-up Work.

After our paper appeared on arXiv, a follow-up work was done by Mannelli et al. [60]. In this paper, the authors consider the same architecture (namely, a shallow network with quadratic activations) under the so-called teacher/student setting and study the landscape of the empirical risk as well as the performance of the gradient flow, the continuous-time analogue of the gradient descent. Importantly, they consider also the regime in which the number $m^{*}$ of the hidden units of the teacher network is less than the dimension d (whereas our focus is on $m^{*}\ge d$). In particular, when $m^{*}=1$, the width m of the student network is at least d, and the data consists of i.i.d. standard normal entries; they prove the following. In the limit as $d\to \infty$, if $n>2d$, then with positive probability the only minimizer of the empirical risk is the matrix $A^{*}$ of teacher weights itself, whereas for $n<2d$, the empirical risk admits spurious minima with probability tending to one. (Namely, the geometry of the empirical risk undergoes a phase transition as $\alpha \triangleq n/d$ crosses ${\alpha }_c=2$). Moreover, they also prove that, for $m\ge d$, the gradient flow converges to a global minima of the empirical risk and to the global minimum of the population risk (which is $A^{*}$) and characterize the rate of convergence for the latter case. (It is worth noting that running gradient flow on the population risk can be perceived as running it on the empirical risk in the limit of the large number n of samples.)

1.1.7. Paper Organization.

In Section 2.1, we present our main results on the landscape of the risk functions, including our energy barrier result for rank-deficient matrices, our result about the absence of full-rank stationary points of the risk function except the globally optimum points, and our result on the convergence of gradient descent. In Section 2.2, we present our results regarding randomly generated weight matrices $W^{*}$ and sufficient conditions for good initializations. In Section 2.3, we study the critical number of training samples guaranteeing good generalization property. We collect useful auxiliary lemmas in Section 3 and provide the proofs of all of our results in Section 4.

1.1.8. Notation.

The set of reals, positive reals, and the set $\{1,2,\dots ,k\}$ are denoted, respectively, by $\mathbb{R},\hspace{0.17em}{\mathbb{R}}_{+}$, and $[k]$. For any matrix A, its smallest and largest singular values, spectrum, trace, Frobenius, and spectral norm are denoted, respectively, by ${\sigma }_{\text{min}}(A),\hspace{0.17em}{\sigma }_{\text{max}}(A),\hspace{0.17em}\sigma (A),\hspace{0.17em}\text{trace}(A),{\Vert A\Vert }_F$, and ${\Vert A\Vert }_2$. We denote the n × n identity matrix by I_n. Planted weights are denoted with an asterisk, for example, $W^{*}$. $\exp (\alpha )$ denotes $e^{\alpha }$. Given any $v\in {\mathbb{R}}^n,{\Vert v\Vert }_2$ denotes its Euclidean ${\mathcal{\ell }}_2$ norm $\sqrt{{\sum }_{1\le i\le n}{v}_i^2}$. Given two vectors $x,y\in {\mathbb{R}}^n$, their Euclidean inner product ${\sum }_{1\le i\le n}{x}_i{y}_i$ is denoted by $〈x,y〉$. Given a collection $Z_1,\dots ,Z_k$ of objects of the same kind (e.g., vectors or matrices), $\text{span}(Z_i:i\in [k])$ is the set, $\{{\sum }_{j=1}^k{\alpha }_j{Z}_j:{\alpha }_j\in \mathbb{R}\}$. We say a random variable X is centered if $\mathbb{E}[X]=0$. $\mathrm{\Theta }(·),O(·),\hspace{0.17em}o(·)$, and $\mathrm{\Omega }(·)$ are standard (asymptotic) order notations for comparing the growth of two sequences. $\widehat{\mathcal{L}}(·),\hspace{0.17em}\nabla \widehat{\mathcal{L}}(·),\hspace{0.17em}\mathcal{L}$, and $\nabla \mathcal{L}$ denote, respectively, the empirical risk, its gradient, and the population risk and its gradient.

2. Main Results

Our main results are now in order.

2.1. Optimization Landscape

2.1.1. Existence of an Energy Barrier.

Our first result shows the presence of an energy barrier in the landscape of the population risk $\mathcal{L}(·)$ below which any rank-deficient $W\in {\mathbb{R}}^{m\times d}$ ceases to exist.

Theorem 1.

Suppose that $X\in {\mathbb{R}}^d$ has i.i.d. centered coordinates with variance μ₂, (finite) fourth moment μ₄, $\text{rank}(W^{*})=d$, and let $\mathcal{L}(W)$ be defined as (3).

1. (Lower bound) It holds that

   $$\underset{W\in {\mathbb{R}}^{m\times d}:\text{rank}(W)<d}{\min } \mathcal{L}(W)\ge \min \{{\mu }_4-{\mu }_2^2,2{\mu }_2^2\}·{\sigma }_{\text{min}}{(W^{*})}^4.$$

2. (Tightness) There exists a matrix $W\in {\mathbb{R}}^{m\times d}$ such that $\text{rank}(W)\le d-1$ and

   $$\mathcal{L}(W)\le \max \left\{{\mu }_4,3{\mu }_2^2\right\}·{\sigma }_{\text{min}}{(W^{*})}^4.$$

The proof of Theorem 1 is deferred to Section 4.2. Two remarks are in order.

First, the hypothesis of Theorem 1 holds under mild distributional assumptions on the coordinates of data: a finite fourth moment and zero mean suffices.

Second, part (b) of Theorem 1 implies that our lower bound on the energy value is tight up to a multiplicative constant determined by the moments of the data. That is, there exists a W with $\text{rank}(W)\le d-1$ such that $\mathcal{L}(W)=\mathrm{\Theta }({\sigma }_{\text{min}}{(W^{*})}^4)$, where the asymptotic $\mathrm{\Theta }(·)$ hides the constants μ₂ and μ₄.

Our next result is an analogue of Theorem 1 for the empirical risk $\widehat{\mathcal{L}}(·)$, and it establishes the presence of a similar energy barrier in the landscape of the empirical risk $\widehat{\mathcal{L}}(·)$ below which any rank-deficient $W\in {\mathbb{R}}^{m\times d}$ ceases to exist with high probability.

Theorem 2.

Let K > 0 be an arbitrary constant and $X_i\in {\mathbb{R}}^d,\hspace{0.17em}1\le i\le N$ be a collection of i.i.d. random vectors each having centered i.i.d. sub-Gaussian coordinates. That is, for some C > 0, $\mathbb{P}(|X(j)|>t)\le \exp (-C{t}^2)$ for every $t\ge 0,\hspace{0.17em}j\in [d]$. Suppose, furthermore, that, for every M > 0, the distribution of X(j), conditional on $|X(j)|\le M$, is centered: $\mathbb{E}[X(j)||X(j)|\le M]=0$. Let $Y_i=f(W^{*};X_i),\hspace{0.17em}1\le i\le N$ be the corresponding label generated by a planted teacher network per (1), where $\text{rank}(W^{*})=d$ and ${\Vert W^{*}\Vert }_F\le d^K$. Then, for some absolute constants $C_3,C\prime >0$ with probability at least

$$1-\exp (-C\prime d)-{\left(9d^{4K+9}\right)}^{d^2-1}·\exp \left(-C_{3}N{d}^{-4-4K}\right)-Nd{e}^{-Cd},$$

it holds that

$$\underset{W\in {\mathbb{R}}^{m\times d}:\text{rank}(W)\le d-1}{\min } \widehat{\mathcal{L}}(W)\triangleq \underset{W\in {\mathbb{R}}^{m\times d}:\text{rank}(W)\le d-1}{\min }\frac{1}{N}{\displaystyle \sum _{1\le i\le N}(Y_i-f(}W;X_i){)}^2\ge \frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4.$$

Here,

$$C_5=\min \{{\mu }_4(1/2)-{\mu }_2{(1/2)}^2,2{\mu }_2{(1/2)}^2\},\hspace{1em}\mathit{\text{where}}\hspace{1em}{\mu }_t(1/2)=\mathbb{E}[X{(j)}^t||X(j)|\le d^{1/2}].$$

Furthermore, if the dimension d of data is constant ($d=O(1)$), then with probability $1-O(1/N)$,

$$\underset{W\in {\mathbb{R}}^{m\times d}:\text{rank}(W)\le d-1}{\min } \widehat{\mathcal{L}}(W)\ge \frac{1}{2}\overline{C_5}{\sigma }_{\text{min}}{(W^{*})}^4,$$

where

$$\overline{C_5}=\min \{{\mu }_4-{\mu }_2^2,2{\mu }_2^2\}\hspace{1em}\mathit{\text{and}}\hspace{1em}{\mu }_n=\mathbb{E}[X{(j)}^n].$$

The proof of Theorem 2 is provided in Section 4.9. Several remarks are now in order.

Assuming d is large, Theorem 2 shows that, with high probability, $\widehat{\mathcal{L}}(W)$ is bounded away from zero by an explicit constant for any W that is rank-deficient provided $N=d^{O(1)}$, where the O(1) term depends on K. Furthermore, provided N is a sufficiently large polynomial-in-d quantity, the probability estimate is of form $1-\exp (-\mathrm{\Theta }(d))$, which is exponential in the dimension.

Note that one indeed needs a finite d correction for the case when the data are low-dimensional, $d=O(1)$: for $d=O(1)$, the term $Nd\exp (-\mathrm{\Theta }(d))$ makes the probability estimate vacuous. The constant $\overline{C_5}$ appearing in this case is precisely the same constant appearing in Theorem 1, and in particular, no conditioning is required. Furthermore, even though we establish the probability estimate to be $1-O(1/N)$ for simplicity, it can be improved: it appears, from our analysis (which uses Chebyshev’s inequality), that for any $\alpha >0$, one can show the probability estimate to be $1-O(N^{-\alpha })$. Furthermore, using more elaborate tools (such as concentration for heavy-tailed variables, in particular, for i.i.d. averages of fourth moments of sub-Gaussian variables), this estimate can potentially be improved to $1-\exp (-{\overline{c}}_0{N}^{c_0})$ for suitable constants $c_0,{\overline{c}}_0>0$. Finally, our analysis yields also that the $1-O(1/N)$ probability estimate still remains valid even when X_i has centered i.i.d coordinates with a finite eight moment. That is, the sub-Gaussianity assumption can be relaxed. Indeed, the expression $\widehat{\mathcal{L}}(W)$ is an i.i.d. sum of the form $N^{-1}{\sum }_{1\le i\le N}{(X_i^{T}M{X}_i)}^2$ for a suitable matrix M, and one needs the finiteness of $\mathbb{E}[{(X^{T}MX)}^4]$ to apply Chebyshev’s inequality: this quantity is finite provided $\mathbb{E}[X_i{(j)}^8]<\infty$ and ${\Vert M\Vert }_F=O(1)$. We do not pursue these extensions for keeping the presentation clear.

We now discuss the assumption that the coordinates of X_i are conditionally centered. This assumption is not inherent to the problem; it is adopted purely for technical reasons. Toward Theorem 2, one needs to establish the existence of an analogous energy barrier for a single rank-deficient $A\in {\mathbb{R}}^{d\times d}$ and should in particular study an event of form

where $C_5(K_1)$ is a certain constant; see Lemma 2. To control $\mathbb{P}[{\mathcal{E}}_A]$, we first condition on an event of the form $\{{\max }_i{\Vert X_i\Vert }_{\infty }\le d^{K_1}\}$ on which the coordinates of X_i are bounded, and we then apply Hoeffding’s inequality to obtain probabilistic guarantees that are exponential in the sample size N. Here, the fact that the coordinates of X_i are conditionally centered makes Theorem 1 applicable; one can then deduce that the conditional mean of ${(X^{T}AX-X^T{(W^{*})}^T{W}^{*}X)}^2$ is at least $C_5(K_1){\sigma }_{\text{min}}{(W^{*})}^4$. Without this assumption, it appears difficult to study the aforementioned probability, and one needs more sophisticated tools. One potential approach is to apply Jensen’s inequality to control the difference between the output of the model with the planted model and then to apply Mendelson’s [61] small ball method; such an argument might, in fact, help relaxing distributional assumptions on X_i. (We thank the anonymous reviewer for suggesting this argument.) The assumption that the conditional mean of $X_i(j)$ is zero is benign; it holds, for example, for random variables whose distributions are symmetric around zero. For instance, any normal distribution with zero-mean satisfies this assumption. Furthermore, Theorem 2 still remains valid even when the coordinates of the data have heavier tails: our techniques apply also to the tails of form $\mathbb{P}(|X_i(j)|>t)\le \exp (-C{t}^{\alpha })$, where $C,\alpha >0$ are arbitrary. We use α = 2 throughout for simplicity.

We next comment on the dependence on ${\Vert W^{*}\Vert }_F$ through the constant K. The (value of) energy barrier is independent of this gap, whereas the probability guarantee does depend on it. This is an artifact of our proof technique. Our proof is based on an ϵ-net argument for a set of rank-deficient matrices with bounded ${\Vert A\Vert }_F$ together with a union bound. The cardinality bound we employ on this net per Lemma 3 depends on d^K; consequently, this constant appears in the probability guarantee. Once again, it might be possible to avoid this by using a different argument as outlined earlier.

An inspection of the proofs of Theorems 1 and 2 yield that the landscapes of the corresponding risks still admit an energy barrier even if we consider the same network architecture with planted weight matrix $W^{*}\in {\mathbb{R}}^{m\times d}$ and quadratic activation function having lower order terms, that is, the activation $\alpha x^2+\beta x+\gamma$ with $\alpha \ne 0$. In this case, in addition to ${\sigma }_{\text{min}}(W^{*})$ and the corresponding moments of the data, the coefficient α also appears in the barrier expression. In particular, Theorem 1 still remains valid with $\min \{{\mu }_4-{\mu }_2^2,2{\mu }_2^2\}·{\sigma }_{\text{min}}{(W^{*})}^4$ replaced with ${\alpha }^2·\min \{{\mu }_4-{\mu }_2^2,2{\mu }_2^2\}·{\sigma }_{\text{min}}{(W^{*})}^4$, and Theorem 2 still remains valid with $\frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4$ replaced with $\frac{{\alpha }^2}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4$.

2.1.2. Global Optimality of Full-Rank Stationary Points.

We now establish that, if W is a full-rank stationary point of the population risk, $\mathcal{L}(·)$, then W is necessarily a global minimum.

Theorem 3.

Suppose $W^{*}\in {\mathbb{R}}^{m\times d}$ with $\text{rank}(W^{*})=d$. Suppose $X\in {\mathbb{R}}^d$ has centered i.i.d. coordinates with $\mathbb{E}[X_i^2]={\mu }_2,\mathbb{E}[X_i^4]={\mu }_4$, and $\text{Var}(X_i^2)>0$. Let $W\in {\mathbb{R}}^{m\times d}$ be a stationary point of the population risk with full-rank, that is, $\nabla \mathcal{L}(W)=\mathbb{E}[\nabla {(f(W^{*};X)-f(W;X))}^2]=0$, and $\text{rank}(W)=d$. Then, $W=Q{W}^{*}$ for some orthogonal matrix Q and that $\mathcal{L}(W)=0$.

The proof of Theorem 3 is deferred to Section 4.6.

Our next result is an analogue of Theorem 3 for the empirical risk, $\widehat{\mathcal{L}}(·)$, and shows that, if $N\ge d(d+1)/2$ and W is any full-rank stationary point of the empirical risk, then W is necessarily a global minimum.

Theorem 4.

Let $X_i\in {\mathbb{R}}^d,\hspace{0.17em}1\le i\le N$, $W^{*}\in {\mathbb{R}}^{m\times d}$ with $\text{rank}(W^{*})=d$, and suppose W is a full-rank stationary point of the empirical risk: $\text{rank}(W)=d$, and ${\nabla }_W\widehat{\mathcal{L}}(W)=0$. Then, $\widehat{\mathcal{L}}(W)=0$. Furthermore, if X_i are i.i.d. random vectors having a jointly continuous distribution and $N\ge d(d+1)/2$, then with probability one, $W=Q{W}^{*}$ for some orthogonal matrix $Q\in {\mathbb{R}}^{m\times m}$.

The proof of Theorem 4 is given in Section 4.10.

Note that an implication of Theorems 3 and 4 is that the corresponding losses admit no full-rank saddle points. Namely, the landscape of the corresponding losses has fairly benign properties below the aforementioned energy barrier. We soon show how this implies the convergence of gradient descent in the next section.

2.1.3. Convergence of Gradient Descent.

We now combine Theorems 1 and 3 to obtain the following conclusion on the performance of the gradient descent algorithm for the population risk. Suppose that the algorithm is initialized at a point W₀ having a small population risk $\mathcal{L}(W_0)$, in particular, lower than the smallest risk value achieved by the rank-deficient matrices. Then, with a properly chosen step size, the algorithm converges to a global optimum: it generates a trajectory ${\{W_k\}}_{k\ge 0}$ of weights such that ${\lim }_{k\to \infty } \mathcal{L}(W_k)={\min }_W \mathcal{L}(W)=0$.

Theorem 5.

Let $W_0\in {\mathbb{R}}^{m\times d}$ be a matrix of weights with the property that

$$\mathcal{L}(W_0)<\underset{W\in {\mathbb{R}}^{m\times d}:\text{rank}(W)<d}{\min } \mathcal{L}(W).$$

Define

$$L=\sup \left\{\Vert {\nabla }^2\mathcal{L}(W)\Vert :\mathcal{L}(W)\le \mathcal{L}(W_0)\right\},$$

where by $\Vert {\nabla }^2\mathcal{L}(W)\Vert$, we denote the spectral norm of the matrix ${\nabla }^2\mathcal{L}(W)$. Then, $L<\infty$ and the gradient descent algorithm with initialization $W_0\in {\mathbb{R}}^{m\times d}$ and any fixed step size of $0<\eta <1/2L$ generates a trajectory ${\{W_k\}}_{k\ge 0}$ of weights such that ${\lim }_{k\to \infty } \mathcal{L}(W_k)={\min }_W \mathcal{L}(W)=0$.

The proof of Theorem 5 is provided in Section 4.7.

Our next focus is on the performance of the gradient descent algorithm for the empirical risk. By combining Theorems 2 and 4, we obtain the following conclusions. Suppose that the gradient descent algorithm is initialized at a point with a sufficiently small empirical risk, in particular, lower than the smallest risk value achieved by rank-deficient matrices (i.e., the energy barrier), and fix an $ϵ>0$. Then, with a properly chosen step size, it finds an approximate stationary point W (that is, a $W\in {\mathbb{R}}^{m\times d}$ with a small ${\Vert \nabla \widehat{\mathcal{L}}(W)\Vert }_F$) in time $\text{poly}({ϵ}^{-1},{\sigma }_{\text{min}}{(W^{*})}^{-1},d)$ for which the weights W^TW are uniformly ϵ-close to the planted weights ${(W^{*})}^T{W}^{*}$, and consequently, the generalization error $\mathcal{L}(W)$ is at most ϵ. Furthermore, the algorithm converges to a global optimum of the empirical risk minimization problem ${\min }_W \widehat{\mathcal{L}}(W)$, which is zero, thus recovering planted weights because of the absence of spurious stationary points within the set of full-rank matrices.

Theorem 6.

Let $ϵ,K>0$ be arbitrary. Suppose that $X_i\in {\mathbb{R}}^d,\hspace{0.17em}1\le i\le N$ satisfies the assumptions in Theorem 2; $W_0\in {\mathbb{R}}^{m\times d}$ is a matrix of weights with the property

$$\widehat{\mathcal{L}}(W_0)<\frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4,$$

where C₅ is the constant defined in Theorem 2 and ${\Vert W^{*}\Vert }_F\le d^K$. Define

$$L=L(W_0)\triangleq \sup \left\{\Vert {\nabla }^2\widehat{\mathcal{L}}(W)\Vert :\widehat{\mathcal{L}}(W)\le \widehat{\mathcal{L}}(W_0)\right\},$$

where by $\Vert {\nabla }^2\widehat{\mathcal{L}}(W)\Vert$, we denote the spectral norm of the (Hessian) matrix ${\nabla }^2\widehat{\mathcal{L}}(W)$ and

$$\zeta \triangleq \min \left\{\frac{ϵ·{\sigma }_{\text{min}}{(W^{*})}^2}{32d^{4K+4}},\frac{{ϵ}^2·{\sigma }_{\text{min}}{(W^{*})}^2}{{(C\prime )}^2{d}^{4K+15}},\frac{ϵ·{\sigma }_{\text{min}}(W^{*})}{2{(C\prime )}^2{\mu }_2^2{d}^{4K+16}}\right\},$$(4)

where $C\prime >0$ is some absolute constant, and ${\mu }_2=\mathbb{E}[X{(j)}^2]$. Then, with probability at least

$$1-\exp (-c\prime N^{1/4})-{\left(9d^{4K+9}\right)}^{d^2-1}·\exp (-C_{4}N{d}^{-4-4K})-Nd\exp (-Cd),$$

(where $c\prime ,C,C_4>0$ are also absolute constants),

1. For any W with $\widehat{\mathcal{L}}(W)<\frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4$, ${\Vert W\Vert }_F\le d^{K+1}$. Moreover, $L=\text{poly}(d)<\infty$.

2. Running gradient descent algorithm starting from W₀ with a step size of $0<\eta <1/2L$ generates a full-rank $W\in {\mathbb{R}}^{m\times d}$ with ${\Vert \nabla \widehat{\mathcal{L}}(W)\Vert }_F\le \zeta$ in time $\text{poly}({ϵ}^{-1},{\sigma }_{\text{min}}{(W^{*})}^{-1},d)$. Furthermore, for this W, $\widehat{\mathcal{L}}(W)\le ϵ$.

3. For W in (b), it holds that ${\Vert W^{T}W-{(W^{*})}^T{W}^{*}\Vert }_F\le ϵ$, and the generalization error $\mathcal{L}(W)$ is at most ϵ provided $N\ge d^{58/3}$.

Furthermore, suppose the data dimension d is constant, $d=O(1)$, and $W_0\in {\mathbb{R}}^{m\times d}$ is a matrix of weights with the property $\widehat{\mathcal{L}}(W_0)<\frac{1}{2}\overline{C_5}{\sigma }_{\text{min}}{(W^{*})}^4$ for the same constant $\overline{C_5}$ appearing in Theorem 2. Then, for ζ chosen per (4), with probability at least $1-O(1/N)$,

1. For any W with $\widehat{\mathcal{L}}(W)\le \frac{1}{2}\overline{C_5}{\sigma }_{\text{min}}{(W^{*})}^4$, it is the case that ${\Vert W\Vert }_F=O(1)$. Moreover, $L=O(1)<\infty$.

2. A running gradient descent algorithm starting from W₀ with a step size of $0<\eta <1/2L$ generates a full-rank W with $\Vert \nabla \widehat{\mathcal{L}}(W)\Vert \le \zeta$ and $\widehat{\mathcal{L}}(W)\le ϵ$.

3. For any W in (b), $\max \{{\Vert W^{T}W-{(W^{*})}^T{W}^{*}\Vert }_F,\mathcal{L}(W)\}\le ϵ$.

The proof of Theorem 6 is provided in Section 4.11. Several remarks are now in order.

As a simple corollary to (b), we, thus, obtain that, for d large enough, the gradient descent algorithm with initialization $W_0\in {\mathbb{R}}^{m\times d}$ and a step size of $0<\eta <1/2L$ generates a trajectory ${\{W_k\}}_{k\ge 0}$ of weights such that ${\lim }_{k\to \infty } \widehat{\mathcal{L}}(W_k)={\min }_W \widehat{\mathcal{L}}(W)=0$. This yields an analogue of Theorem 5 for the empirical risk, $\widehat{\mathcal{L}}(·)$.

Note that, when N is a sufficiently large polynomial-in-d function, the probability estimate for the first part is essentially $1-\exp (-\mathrm{\Theta }(d))$. Furthermore, we note that the exponent 1/4 in the probability estimate and the sample bound $d^{58/3}$ are required only for part (c) and can potentially be improved. In particular, the exponent can be improved to one for parts (a), (b), and (d).

We now expand on the sample complexity $d^{58/3}$ per part $(\text{c})$, which appears rather poor. In light of Soltanolkotabi et al. [83], a much smaller sample complexity of $O(d^2)$ suffices to obtain an approximate stationary point W. Our work, on the other hand, takes a step further: we control the deviation of W^TW from ${(W^{*})}^T{W}^{*}$ and, subsequently, bound the generalization error. As we mention earlier, we are unaware of similar guarantees in the literature; the prior work, in fact, seems to focus only on minimizing the training error. This extension is based on a certain technical result established in Emschwiller et al. [33] (see the following for details), and the sample bound is likely to be an artifact of this approach. Having said this, it might though be possible to improve the dependence on dimension d. As a potential avenue, one may consider leveraging techniques from the phase retrieval literature, such as PhaseLift (Candès and Li [13], Candès et al. [15], Demanet and Hand [22], Eldar and Mendelson [32]), or from the matrix sensing literature mentioned earlier. It appears that some of these algorithms solve a certain convex relation, and the fact that the underlying matrix to be recovered is low rank is crucial for this convex program. In our case, $W^{*}$ and, therefore, ${(W^{*})}^T{W}^{*}$ are full rank, so it is not clear whether these algorithms would apply as is. In fact, as mentioned earlier, closely related works in the matrix sensing literature address a (variant of) an empirical risk minimization problem though they do not quantify how close the obtained solution and the ground truth are. The connection between our model and the phase retrieval/matrix sensing literature is very intriguing; it is plausible that the algorithms in the latter domain might apply to our case. This direction merits further investigation and is left for future work.

Note again that, analogous to Theorem 2, one needs a correction for the finite d case because the term $Nd\exp (-\mathrm{\Theta }(d))$ makes the probability estimate vacuous for $d=O(1)$. Furthermore, the remarks following Theorem 2 still remain valid. In particular, the choice of $1-O(1/N)$ is for simplicity, and the estimate can be improved almost immediately to $1-O(N^{-\alpha })$ for any $\alpha >0$ and to $1-\exp (-{\overline{c}}_0{N}^{c_0})$ for some $c_0,{\overline{c}}_0>0$ using more delicate concentration tools.

We now provide an important remark pertaining to (c): as we show in the proof, provided N grows at least polynomially in d, with probability $1-\exp (-C\prime N^{1/4})$ over X_i, it holds that, for any W having a small risk, $\widehat{\mathcal{L}}(W)$, W^TW is close to ${(W^{*})}^T{W}^{*}$: ${\Vert W^{T}W-{(W^{*})}^T{W}^{*}\Vert }_F$ is small. Consequently, $\mathcal{L}(W)$ is small. This is one of the additional technical results of our paper and is achieved by controlling the condition number of a certain matrix whose i.i.d. rows consist of the tensorized data $X_i^{\otimes 2}$. The proof uses a recent work analyzing the spectrum of expected covariance matrices of tensorized data (Emschwiller et al. [33, theorem 5.1]). It is worth highlighting that the independence of the coordinates of X_i is crucial for establishing Theorem 6. Our results leverage techniques in Emschwiller et al. [33] and require, in particular, that the coordinates of X_i are samples from an admissible distribution in the sense of Emschwiller et al. [33, definition 2.4, theorem 5.1]; they would no longer be valid if X_i had potentially dependent coordinates.

These results concern the performance of gradient descent assuming the initialization is proper, that is, it is below the aforementioned energy barrier. One can then naturally ask whether such an initialization is indeed possible in some generic context. In the next section, we address this question of proper initialization when the (planted) weights are generated randomly in order to complement Theorems 5 and 6. We establish that such a proper initialization is indeed possible by providing a deterministic initialization guarantee, which, with high probability, beats the aforementioned energy barrier.

Remark 1.

Before we close this section, we remark on the full-rank assumption, $\text{rank}(W^{*})=d$. This assumption can be relaxed for Theorems 1 and 2, and one can establish a similar energy barrier for all W with $\text{rank}(W)<\text{rank}(W^{*})$. For instance, suppose $\text{rank}(W^{*})=d-1$ and $\text{rank}(W)\le d-2$. Using an eigenvalue interlacing argument (see, e.g., Fulton [35, equation 11]), one can subsequently modify the proofs of Theorems 1 and 2 and obtain a similar energy barrier for all W whose rank is strictly below that of planted $W^{*}$. On the other hand, the full-rank assumption appears necessary for the results regarding stationary points and global optimality (Theorems 3 and 4) and the subsequent convergence guarantees regarding the gradient descent (Theorems 5 and 6). In fact, a similar full-rank assumption to rule out spurious local minima is also employed in the very related work Soltanolkotabi et al. [83, theorem 2.2] discussed earlier. One of their results (Soltanolkotabi et al. [83, theorem 2.1]) seems to avoid this though at the expense of a rather unnatural assumption that the output layer contains at least d positive and d negative entries. Inspecting their proof as well as ours, a full-rank assumption or the assumption that the output layer has d positive and d negative entries seem crucial: to study the gradient of a stationary point and subsequently declare global optimality, it appears necessary to show that the kernel of a certain matrix arising in the gradient calculation is trivial. It would be interesting to see to which extent this assumption can be relaxed or whether it can be avoided altogether; we leave this as an interesting open direction for future work.

2.2. On Initialization: Randomly Generated Planted Weights

Our results in the previous section show that, provided the initialization of the gradient descent method occurs below the critical energy, the algorithm converges to the global minimum. This raises the question whether such an initialization can be found in a constructive way.

In this section, we show that the answer is yes in the setting of randomly generated weights of the ground truth matrix $W^{*}$. Specifically, we provide a way to properly initialize such networks under the assumption that the (planted) weight matrix $W^{*}\in {\mathbb{R}}^{m\times d}$ has arbitrary i.i.d. centered entries with unit variance and a finite fourth moment and the data has centered i.i.d. sub-Gaussian coordinates. (It is worth mentioning that, similar to before, the sub-Gaussianity assumption on the data are required only for the case of empirical risk, and the corresponding population risk result holds under a milder distributional assumption; see Theorem 7.) Our result is valid provided that the network is sufficiently overparameterized: $m>C{d}^2$ for some large constant C. Note that this implies $W^{*}$ is a tall matrix sending ${\mathbb{R}}^d$ into ${\mathbb{R}}^m$. The rationale behind this approach is as follows. The value of the risk is determined by the spectrum of $\mathrm{\Delta }\triangleq W^{T}W-{(W^{*})}^T{W}^{*}$ and the moments of the data distribution. Under our randomness assumption, the so-called Wishart matrix ${(W^{*})}^T{W}^{*}$ is tightly concentrated around a multiple of the identity if m is sufficiently large. Hence, one can control the spectrum of Δ and, therefore, the loss functions ($\mathcal{L}$ and $\widehat{\mathcal{L}}(·)$) by properly choosing the initialization W.

We now state the main results of this section, starting with the population risk version.

Theorem 7.

Suppose that the data $X\in {\mathbb{R}}^d$ consists of i.i.d. centered coordinates with $\text{Var}(X_i^2)>0$ and $\mathbb{E}[X_i^4]<\infty$. Recall $\mathcal{L}(W)$ from (3).

1. (Gaussian case) Suppose that the planted weight matrix $W^{*}\in {\mathbb{R}}^{m\times d}$ has i.i.d. standard normal entries. Let the initial weight matrix $W_0\in {\mathbb{R}}^{m\times d}$ be defined by ${(W_0)}_{i,i}=\sqrt{m+4d}$ for $1\le i\le d$ and ${(W_0)}_{i,j}=0$ otherwise; that is, $W_0^T{W}_0=\gamma I_d$ with $\gamma =m+4d$. Then, provided $m>C{d}^2$ for a sufficiently large absolute constant C > 0,

   $$\mathcal{L}(W_0)<\underset{W\in {\mathbb{R}}^{m\times d}:\text{rank}(W)<d}{\min } \mathcal{L}(W),$$
   with probability at least $1-\exp (-\mathrm{\Omega }(d))$, where the probability is with respect to the draw of $W^{*}$.

2. (General case) Suppose the planted weight matrix $W^{*}\in {\mathbb{R}}^{m\times d}$ has centered i.i.d. entries with unit variance and a finite fourth moment. Let the initial weight matrix $W_0\in {\mathbb{R}}^{m\times d}$ be defined by ${(W_0)}_{i,i}=\sqrt{m}$ for $1\le i\le d$, and ${(W_0)}_{i,j}=0$ otherwise; that is, $W_0^T{W}_0=m{I}_d$. Then, provided $m>C{d}^2$ for a sufficiently large absolute constant C > 0,

   $$\mathcal{L}(W_0)<\underset{W\in {\mathbb{R}}^{m\times d}:\text{rank}(W)<d}{\min } \mathcal{L}(W),$$
   with high probability as $d\to \infty$, where the probability is with respect to the draw of $W^{*}$.

The proof of this theorem is provided in Section 4.8.

Note that, part (a) of Theorem 7 gives an explicit rate for probability in the case when the i.i.d. entries of the planted weight matrix $W^{*}$ are standard normal and is based on a nonasymptotic concentration result for the spectrum of such matrices. The extension in part (b) is based on a semicircle law obtained by Bai and Yin [3].

The corresponding result for the empirical risk is provided as follows.

Theorem 8.

Suppose that the planted weight matrix $W^{*}\in {\mathbb{R}}^{m\times d}$ has centered i.i.d. entries with unit variance and a finite fourth moment; the (i.i.d.) data $X_i\in {\mathbb{R}}^d,\hspace{0.17em}1\le i\le N$, has i.i.d. centered sub-Gaussian coordinates (namely, for some C > 0, $\mathbb{P}(|X_i(j)|>t)\le \exp (-C{t}^2)$ for any t > 0, $1\le i\le N$ and $1\le j\le d$) and the $W_0\in {\mathbb{R}}^{m\times d}$ satisfies ${(W_0)}_{ii}=\sqrt{m}$ for $i\in [d]$ and ${(W_0)}_{ij}=0$ for $i\ne j$, that is, $W_0^T{W}_0=m{I}_d\in {\mathbb{R}}^{d\times d}$. Then, for some absolute constants $C,C\prime >0$ with probability at least

$$1-\exp \left(-C\prime \frac{N}{d^{5}m}\right)-Nd\exp (-Cd)-o_d(1),$$

it is the case that, for the constant C₅ defined in Theorem 2,

$$\widehat{\mathcal{L}}(W_0)<\frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4$$

provided $m>C^{″}{d}^2$ for a sufficiently large constant $C^{″}>0$.

The proof of Theorem 8 is provided in Section 4.12.

It is worth noting that, unlike the earlier Theorems 2 and 6, Theorems 7 and 8 do not have a separate statement for the case of finite d ($d=O(1)$): in order to ensure the concentration property for the Wishart ensemble takes place, one should consider the regime $d\to \infty$. That is, our initialization results do not hold for the regime in which d is constant.

We highlight that, for low-rank models, such as the problem of sensing a low-rank matrix described earlier as well as learning quadratic networks with a low-rank weight matrix $W^{*}$, prior work proposes spectral initialization (Gunasekar et al. [41], Khodak et al. [52], Li et al. [57], Stöger and Soltanolkotabi [87], Vodrahalli et al. [92]) and analyzes the performance of gradient descent in recovering the planted weights. More concretely, for recovering an unknown rank-r matrix $A^{*}\in {\mathbb{R}}^{d\times d}$, these works propose initializations of the form UU^T, where $U\in {\mathbb{R}}^{d\times r}$. For our results, in particular, the global optimality of certain stationary points (Theorems 3 and 4) as well as the convergence guarantees for the gradient descent (Theorems 5 and 6), the fact that $W^{*}$ is full rank is crucial. Even though such a low-rank initialization would not suffice for the goal of finding a W₀ with loss below the energy barrier, it would be interesting to analyze the performance of such an initialization for a higher number of iterations. If successful, such an initialization would enable us to relax the randomness assumption on $W^{*}$; we leave this as an interesting future direction.

We now turn our attention to the number of training samples required to learn such models.

2.3. Critical Number of Training Samples

In this section, we explore the smallest number of training data for which a small empirical risk controls the generalization error.

2.3.1. A Necessary and Sufficient Geometrical Condition.

We start by identifying a necessary and sufficient geometrical condition on the data under which any minimizer of the empirical risk has zero generalization error. For our setting, any such minimizer necessarily interpolates the data.

Theorem 9.

Let $X_1,\dots ,X_n\in {\mathbb{R}}^d$ be a set of data. Let (P) be the property that $\text{span}\{X_i{X}_i^T:1\le i\le N\}=\mathcal{S}$, where $\mathcal{S}$ is the set of all d × d symmetric real matrices.

1. Suppose that (P) holds. Then, for any $\widehat{m}\in \mathbb{N}$ and $W\in {\mathbb{R}}^{\widehat{m}\times d}$ satisfying $f(W^{*};X_i)=f(W;X_i),\forall i\in [N]$, we have $W^{T}W={(W^{*})}^T{W}^{*}$. In particular, if $\widehat{m}\ge m$, then $W=Q{W}^{*}$ for some $Q\in {\mathbb{R}}^{\widehat{m}\times m}$ with $Q^{T}Q=I_m$.

2. Suppose that (P) does not hold. Then, for any $W^{*}\in {\mathbb{R}}^{m\times d}$ with $\text{rank}(W^{*})=d$ and any $\widehat{m}\ge d$, there exists a $W\in {\mathbb{R}}^{\widehat{m}\times d}$ such that, whereas $f(W^{*};X_i)=f(W;X_i),\forall i\in [N],\hspace{0.17em}{W}^{T}W\ne {(W^{*})}^T{W}^{*}$. In particular, almost surely $\mathcal{L}(W)>0$ with respect to any jointly continuous distribution on ${\mathbb{R}}^d$.

The proof of Theorem 9 is provided in Section 4.13.

Note that the property (P), $\text{span}\{X_i{X}_i^T:i\in [N]\}=\mathcal{S}$, is a purely geometrical necessary and sufficient condition; it can be checked ahead of the optimization (not retrospective). Under (P), any minimizer of empirical risk $\widehat{\mathcal{L}}$ has perfect generalization. Conversely, when (P) does not hold, there are global optima of $\widehat{\mathcal{L}}$ that (almost surely) have a strictly positive generalization error. Furthermore, Theorem 9 applies to any arbitrary data set X_i (not necessarily random). We highlight the extension that, when $\widehat{\mathcal{L}}(W)$ is positive though small, one can control ${\Vert W^{T}W-{(W^{*})}^T{W}^{*}\Vert }_F$ via Theorem 5(c) and bound $\mathcal{L}(W)$. For a more refined version of Theorem 9, see Theorem 11.

We next highlight the parameter $\widehat{m}\in \mathbb{N}$. Note that, when (P) holds, any network with $\widehat{m}$ nodes interpolating the data necessarily has zero generalization error. This holds even in the overparameterized regime, $\widehat{m}\ge m$. Namely, once the data are interpolated, overparameterization does not hurt the generalization ability. This is an instance of an empirically observed (and extensively studied) phenomenon regarding neural networks that defies classical statistical wisdom.

Finally, Theorem 9 still holds if each node has an associated positive output weight $a_j^{*}\in {\mathbb{R}}^{+}$, that is if the network computes ${\sum }_{j\le m}{a}_j^{*}{〈W_j^{*},X〉}^2$. This is easily seen by pushing $a_j^{*}$ inside $W_j^{*}$.

2.3.2. Randomized Data Enjoys the Geometric Condition.

We now identify the smallest number $N^{*}$ of training samples such that random data $X_i,i\in [N]$ almost surely satisfies (P) for $N\ge N^{*}$.

Theorem 10.

Let $N^{*}=d(d+1)/2$ and $X_1,\dots ,X_N\in {\mathbb{R}}^d$ be i.i.d. random vectors with a jointly continuous distribution. Then,

1. If $N\ge N^{*}$, then $\mathbb{P}(\text{span}(X_i{X}_i^T:i\in [N])=\mathcal{S})=1$.

2. If $N<N^{*}$, then for arbitrary $Z_1,\dots ,Z_N\in {\mathbb{R}}^d,\hspace{0.17em}\text{span}(Z_i{Z}_i^T:i\in [N])⊊\mathcal{S}$.

Theorem 10 is likely folklore; we provide a proof in Section 4.14 for completeness. Observe that part (b) is straightforward: as $N^{*}=(\begin{array}{c}d\\ 2\end{array})+d=\text{dim}(\mathcal{S})$, (P) cannot hold when $N<N^{*}$.

2.3.3. Sample Complexity Bound for the Planted Network Model.

Combining Theorems 9 and 10, we arrive at the following sample complexity result.

Theorem 11.

Let $X_i,i\in [N]$ be i.i.d. samples drawn from a jointly continuous distribution on ${\mathbb{R}}^d$ and $Y_i=f(W^{*};X_i)$, where $W^{*}\in {\mathbb{R}}^{m\times d}$ with $\text{rank}(W^{*})=d$.

1. Suppose $N\ge N^{*}$, and $\widehat{m}\in \mathbb{N}$. Then, with probability one over $X_1,\dots ,X_N$, the following holds. If $W\in {\mathbb{R}}^{\widehat{m}\times d}$ with $f(W;X_i)=Y_i,\forall i\in [N]$, then $f(W;x)=f(W^{*};x)$ for all $x\in {\mathbb{R}}^d$.

2. Suppose $X_i\in {\mathbb{R}}^d,i\in [N]$ are i.i.d., each with centered i.i.d. entries having variance μ₂ and a finite fourth moment μ₄. Suppose $N<N^{*}$. Then, there exists a $W\in {\mathbb{R}}^{m\times d}$ such that $f(W;X_i)=Y_i,\forall i\in [N]$, but $\mathcal{L}(W)\ge \min \{{\mu }_4-{\mu }_2^2,2{\mu }_2^2\}·{\sigma }_{\text{min}}{(W^{*})}^4$.

The proof of Theorem 11 is provided in Section 4.15.

The lower bound in part (b) is very similar to the energy barrier for rank-deficient matrices per Theorems 1(a) and 2. Moreover, the interpolating network in (a) can be overparameterized. Theorem 11 provides the necessary and sufficient number of data points for training a shallow quadratic network so as to guarantee perfect generalization property.

2.3.4. Related Work.

We now discuss a related line of work on polynomial activations that seek necessary and sufficient conditions and/or the smallest sample size under which the loss functions satisfy various favorable properties. Venturi et al. [90] study a key topological property of the loss function, namely, the presence/absence of spurious valleys. Similar to us, they identify necessary and sufficient conditions independent of the data distribution. One of their results (Venturi et al. [90, corollary 9]) shows that the empirical risk $\widehat{\mathcal{L}}$ admits no spurious valleys provided the network is sufficiently overparameterized: $m\ge N$, where N is the sample size. (A close variant of this result is in fact shown earlier by Livni et al. [59]; see Venturi et al. [90] for a comparison.) Moreover, they also establish a similar guarantee regarding the population risk for quadratic networks; see Venturi et al. [90, theorem 12]. Similar analysis for quadratic networks is conducted also by Soltanolkotabi et al. [83] and Du et al. [24] mentioned earlier. In particular, Soltanolkotabi et al. [83] establish the absence of spurious local minima for $\widehat{\mathcal{L}}$ when $d\le N\le O(d^2)$; Du et al. [24] establish that a regularized version of the empirical risk has no spurious minima when (a) m > d or (b) $m(m+1)\ge 2n$ and m < d. Yet another related work by Mannelli et al. [60] show the following when the data has i.i.d. standard normal entries. For $n>2d$, the only minimizer of the empirical risk is a planted weight matrix, whereas for $n<2d$, the empirical risk admits spurious local minima, both w.h.p. as $n,d\to \infty$.

3. Preliminaries

We collect herein several useful auxiliary results that we employ in our proofs.

3.1. An Analytical Expression for the Population Risk

Toward proving our energy barrier results, Theorems 2 and 1, we start with providing an analytical expression for the population risk $\mathcal{L}(W)$ of any $W\in {\mathbb{R}}^{m\times d}$ in terms of how close it is to the planted weight matrix $W^{*}\in {\mathbb{R}}^{m\times d}$.

We recall that a random vector X in ${\mathbb{R}}^d$ is defined to have a jointly continuous distribution if there exists a measurable function $f:{\mathbb{R}}^d\to \mathbb{R}$ such that, for any $i\in [N]$ and Borel set $\mathcal{B}\subseteq {\mathbb{R}}^d$,

where λ is the Lebesgue measure on ${\mathbb{R}}^d$.

Theorem 12.

Let $W^{*}\in {\mathbb{R}}^{m\times d},\hspace{0.17em}f(W^{*};X)$ be the function computed by (1) and $f(W;X)$ be similarly the function computed by (1) for $W\in {\mathbb{R}}^{m\times d}$. Recall,

$$\mathcal{L}(W)=\mathbb{E}[{(f(W^{*};X)-f(W;X))}^2],$$

where the expectation is with respect to the distribution of $X\in {\mathbb{R}}^d$.

1. Suppose the distribution of X is jointly continuous. Then, $\mathcal{L}(W)=0$, that is, $f(W^{*};X)=f(W;X)$ almost surely with respect to X if and only if $W=Q{W}^{*}$ for some orthonormal matrix $Q\in {\mathbb{R}}^{m\times m}$. Suppose now that the coordinates of $X\in {\mathbb{R}}^d$ are i.i.d. with $\mathbb{E}[X_i]=0,\mathbb{E}[X_i^2]={\mu }_2$, and $\mathbb{E}[X_i^4]={\mu }_4$.

2. It holds that

   $$\mathcal{L}(W)={\mu }_2^2·\text{trace}{(A)}^2+2{\mu }_2^2·\text{trace}(A^2)+({\mu }_4-3{\mu }_2^2)·\text{trace}(A\circ A),$$
   where $A={(W^{*})}^T{W}^{*}-W^{T}W\in {\mathbb{R}}^{d\times d}$ and $A\circ A$ is the Hadamard product of A with itself. In particular, if $X\in {\mathbb{R}}^d$ has i.i.d. standard normal coordinates, we obtain $\mathcal{L}(W)=\text{trace}{(A)}^2+2\text{trace}(A^2)$.

3. The following bounds hold:

   $${\mu }_2^2·\text{trace}{(A)}^2+\min \left\{{\mu }_4-{\mu }_2^2,2{\mu }_2^2\right\}·\text{trace}(A^2)\le \mathcal{L}(W),$$
   and
   $${\mu }_2^2·\text{trace}{(A)}^2+\max \left\{{\mu }_4-{\mu }_2^2,2{\mu }_2^2\right\}·\text{trace}(A^2)\ge \mathcal{L}(W).$$

The proof of Theorem 12 is provideed in Section 4.1.

In a nutshell, Theorem 12 states that the population risk $\mathcal{L}(W)$ of any $W\in {\mathbb{R}}^d$ is completely determined by how close it is to the planted weights $W^{*}$ as measured by the matrix $A={(W^{*})}^T{W}^{*}-W^{T}W$ and the second and fourth moments of the data. This is not surprising: $\mathcal{L}(W)$ is essentially a function of the first four moments of the data and the difference of the quadratic forms generated by W and $W^{*}$, which is precisely encapsulated by the matrix A. Note also that the characterization of the optimal orbit per part (a) is not surprising either: any matrix W with the property $W=Q{W}^{*}$, where $Q\in {\mathbb{R}}^{m\times m}$ is an orthonormal matrix, that is, $Q^{T}Q=I_m$, has the property that $f(W;X)={\Vert WX\Vert }_2^2=X^T{W}^{T}WX=f(W^{*};X)$ for any data $X\in {\mathbb{R}}^d$. Part (a) then says the reverse is true as well provided that the distribution of X is jointly continuous. Note also that, for X with centered i.i.d. entries, the thesis of part (a) follows also from part (c): $\mathcal{L}(W)=0$ implies that $\text{trace}(A^2)=0$, which, together with the fact that A is symmetric, then yields A = 0; that is, $W^{T}W={(W^{*})}^T{W}^{*}$.

3.2. Useful Lemmas and Results from Linear Algebra and Random Matrix Theory

Our next result is a simple norm bound for the ensemble $X_i\in {\mathbb{R}}^d,\hspace{0.17em}1\le i\le N$ with sub-Gaussian coordinates.

Lemma 1.

Let $X_i\in {\mathbb{R}}^d,\hspace{0.17em}1\le i\le N$ be an i.i.d. collection of random vectors with centered i.i.d. sub-Gaussian coordinates, that is, for some constant C > 0, $\mathbb{P}(|X_i(j)|>t)\le \exp (-C{t}^2)$ for every $i\in [N],j\in [d]$, and $t\ge 0$. Then,

$$\mathbb{P}\left({\Vert X_i\Vert }_{\infty }\le d^{K_1},1\le i\le N\right)\ge 1-Nd\exp (-C{d}^{2K_1}).$$

The proof of Lemma 1 is provided in Section 4.3.

Our energy barrier result Theorem 2 for the empirical risk is proven by establishing the emergence of a barrier for a single rank-deficient $A\in {\mathbb{R}}^{d\times d}$ together with a covering numbers argument.

Lemma 2.

Let $K_1>0$ be an arbitrary constant and $X_i\in {\mathbb{R}}^d,\hspace{0.17em}1\le i\le N$ be a collection of i.i.d. data with centered i.i.d. sub-Gaussian coordinates for which for any M > 0, the mean of $|X_1(1)|$ conditional on $|X_1(1)|\le M$ is zero, and let $Y_i=f(W^{*};X_i)$ be the corresponding label generated by a neural network with planted weights $W^{*}\in {\mathbb{R}}^{m\times d}$ as per (1), where ${\Vert W^{*}\Vert }_F\le d^{K_2}$. Fix any $A\in {\mathbb{R}}^{d\times d}$, where ${\Vert A\Vert }_F\le d^{2K_2},\hspace{0.17em}\text{rank}(A)\le d-1$, and $A⪰0$. Define the event

$$\mathcal{E}(A)\triangleq \left\{\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{\left(Y_i-X_i^{T}A{X}_i\right)}^2}\ge \frac{1}{2}{C}_5(K_1){\sigma }_{\text{min}}{(W^{*})}^4\right\},$$

where

$$C_5(K_1)\triangleq \min \{{\mu }_4(K_1)-{\mu }_2{(K_1)}^2,2{\mu }_2{(K_1)}^2\}$$

for ${\mu }_n(K)=\mathbb{E}[X_1{(1)}^n||X_1(1)|\le d^K]$. Then, there exists a constant $C\prime >0$ (independent of W and depending only on data distribution, K₁, and $W^{*}$) such that

$$\mathbb{P}(\mathcal{E}{(A)}^c|{\Vert X_i\Vert }_{\infty }\le d^{K_1},1\le i\le N)\le \exp \left(-C_3\frac{N}{d^{4K_1+4K_2+2}}\right).$$

In particular,

$$\mathbb{P}(\mathcal{E}(A))\ge 1-\exp \left(-C_3\frac{N}{d^{4K_1+4K_2+2}}\right)-Nd{e}^{-C{d}^{2K_1}},$$

where C > 0 is the same constant as in Lemma 1.

The parameter K₁ appearing in Lemma 2 controls the amount of truncation applied on training data, and K₂ controls the norm of the planted weight matrix. The proof of Lemma 2 is provided in Section 4.4.

The next result is a covering number bound adopted from Candès and Plan [14, lemma 3.1] with minor modifications.

Lemma 3.

Let

$$S_R\triangleq \left\{A\in {\mathbb{R}}^{d\times d}:\text{rank}(A)\le r,A⪰0,{\Vert A\Vert }_F\le R\right\}.$$

Then, there exists a $ϵ-$net $\overline{S_R}$ for S_R in the Frobenius norm (that is, for every $A\in S_R$, there exists an $\widehat{A}\in \overline{S_R}$ such that ${\Vert A-\widehat{A}\Vert }_F\le ϵ$) such that

$$|\overline{S_R}|\le {\left(\frac{9R}{ϵ}\right)}^{dr+r}.$$

The proof of Lemma 3 is provided in Section 4.5.

Some of our results use the following well-known results. These results are verbatim from the literature and provided herein without proof.

Theorem 13

(Caron and Traynor [16]). Let $\mathcal{\ell }$ be an arbitrary positive integer and $P:{\mathbb{R}}^{\mathcal{\ell }}\to \mathbb{R}$ be a polynomial. Then, either P is identically zero or $\{x\in {\mathbb{R}}^{\mathcal{\ell }}:P(x)=0\}$ has zero Lebesgue measure, namely, P(x) is nonzero almost everywhere.

Theorem 14

(Horn and Johnson [47, Theorem 7.3.11]). For two matrices $A\in {\mathbb{R}}^{p\times n}$ and $B\in {\mathbb{R}}^{q\times n}$, where $q\le p$, $A^{T}A=B^{T}B$ holds if and only if A = QB for some matrix $Q\in {\mathbb{R}}^{p\times q}$ with orthonormal columns.

Our results regarding the initialization guarantees use the several auxiliary results from random matrix theory: the spectrum of tall random matrices are essentially concentrated.

Theorem 15

(Vershynin [91, Corollary 5.35]). Let A be an m × d matrix with independent standard normal entries. For every $t\ge 0$, with probability at least $1-2 \exp (-t^2/2)$, we have

$$\sqrt{m}-\sqrt{d}-t\le {\sigma }_{\text{min}}(A)\le {\sigma }_{\text{max}}(A)\le \sqrt{m}+\sqrt{d}+t.$$

Theorem 16

(Bai and Yin [4], Vershynin [91, Theorem 5.31]). Let $A=A_{N,n}$ be an N × n random matrix whose entries are independent copies of a random variable with zero mean, unit variance, and a finite fourth moment. Suppose that the dimensions N and n grow to infinity and the aspect ratio n/N converges to a constant in $[0,1]$. Then,

$${\sigma }_{\text{min}}(A)=\sqrt{N}-\sqrt{n}+o(\sqrt{n}),\hspace{1em}\mathit{\text{and}}\hspace{1em}{\sigma }_{\text{min}}(A)=\sqrt{N}+\sqrt{n}+o(\sqrt{n}),$$

almost surely.

The following concentration result, recorded herein verbatim from Vershynin [91], is useful for our approximate stationarity analysis.

Theorem 17

(Vershynin [91, Theorem 5.44]). Let A be an N × n matrix whose rows A_i are independent random vectors in ${\mathbb{R}}^n$ with the common second moment matrix $\mathrm{\Sigma }=\mathbb{E}[A_i{A}_i^T]$. Let m be a number such that ${\Vert A_i\Vert }_2\le \sqrt{m}$ almost surely for all i. Then, for every $t\ge 0$, the following inequality holds with probability at least $1-n·\exp (-c{t}^2)$:

$$\Vert \frac{1}{N}{A}^{T}A-\mathrm{\Sigma }\Vert \le \max \left({\Vert \mathrm{\Sigma }\Vert }^{1/2}\delta ,{\delta }^2\right)\hspace{1em}\mathit{\text{where}}\hspace{1em}\delta =t\sqrt{m/N}.$$

Here, c > 0 is an absolute constant.

Finally, we make use of the matrix-operator version of Hölder’s inequality.

Theorem 18

(Bhatia [8]). For any matrix $U\in {\mathbb{R}}^{k\times \mathcal{\ell }}$, let ${\Vert U\Vert }_{{\sigma }_p}$ denotes the ${\mathcal{\ell }}_p$ norm of the vector

$$({\sigma }_1(U),\dots ,{\sigma }_{\min \{k,\mathcal{\ell }\}}(U))$$

of singular values of U. Then, for any $p,q>0$ with $\frac{1}{p}+\frac{1}{q}=1$, it holds that

$$|〈U,V〉|=|\text{trace}(U^{T}V)|\le {\Vert U\Vert }_{{\sigma }_p}{\Vert V\Vert }_{{\sigma }_q}.$$

4. Proofs

In this section, we present the proofs of the main results of this paper.

The order of the proofs presented herein is slightly different from the order of the corresponding results in the main body in that none of the following proofs (with one exception that we detail) use a proof presented later than itself. That is, whenever we present the proof of a result, it is ensured that, if this proof requires another result as a building block, this building block is shown earlier. The rationale behind this is to avoid any potential confusion and to ensure that no cyclic reasoning is present.

With this arrangement, only Theorem 4 uses results presented later in this section (more precisely, it uses Theorems 9 and 10), and it can be checked directly that there is no cyclic reasoning in the proof of Theorem 4.

4.1. Proof of Theorem 12

First, we have

where $A={(W^{*})}^T{W}^{*}-W^{T}W\in {\mathbb{R}}^{d\times d}$ is a symmetric matrix. Note also thatandwhere A² is equal to $A^{T}A$ as A is symmetric.

1. Recall Theorem 13. In particular, if $\mathcal{L}(W)=0$, then we have $P(X)=X^{T}AX=0$ almost surely. Because $P(·):{\mathbb{R}}^d\to \mathbb{R}$ a polynomial, it then follows that P(X) = 0 identically. Now, because A is symmetric, it has real eigenvalues, called ${\lambda }_1,\dots ,{\lambda }_d$ with corresponding (real) eigenvectors ${\xi }_1,\dots ,{\xi }_d$. Now, taking $X={\xi }_i$, we have $X^{T}AX={\xi }_i^{T}A\xi ={\lambda }_i〈{\xi }_i,{\xi }_i〉=0$. Because ${\xi }_i\ne 0$, we get ${\lambda }_i=0$ for any i. Finally, because $A=Q\mathrm{\Lambda }{Q}^T$, it must necessarily be the case that A = 0. Hence, $W^{T}W={(W^{*})}^T{W}^{*}$, which implies $W=Q{W}^{*}$ for some $Q\in {\mathbb{R}}^{m\times m}$ orthonormal, per Theorem 14.

2. Using Equation (5), we first have

   $$\mathcal{L}(W)={\displaystyle \sum _{1\le i,j,i\prime ,j\prime \le d}{A}_{ij}}{A}_{i\prime ,j\prime }\mathbb{E}\left[X_i{X}_j{X}_{i\prime }{X}_{j\prime }\right].$$

   Note that, if $|\{i,j,i\prime ,j\prime \}|\in \{3,4\}$, then $\mathbb{E}[X_i{X}_j{X}_{i\prime }{X}_{j\prime }]=0$ because X has centered i.i.d. coordinates. Keeping this in mind and carrying out the algebra, we then get

   $$\begin{array}{ll}\mathcal{L}(W)\hfill & ={\displaystyle \sum _{i=1}^d{A}_{ii}^2}\mathbb{E}\left[X_i^4\right]+2{\displaystyle \sum _{i<j}{A}_{ii}}{A}_{jj}\mathbb{E}\left[X_i^2\right]\mathbb{E}\left[X_j^2\right]+4{\displaystyle \sum _{i<j}{A}_{ij}^2}\mathbb{E}\left[X_i^2\right]\mathbb{E}\left[X_j^2\right]\hfill \\ \hfill & ={\mu }_4{\displaystyle \sum _{i=1}^d{A}_{ii}^2}+2{\mu }_2^2{\displaystyle \sum _{i<j}{A}_{ii}}{A}_{jj}+4{\mu }_2^2{\displaystyle \sum _{i<j}{A}_{ij}^2}.\hfill \end{array}$$

   Using now Equations (6) and (7), we get

   $$\mathcal{L}(W)=({\mu }_4-3{\mu }_2^2)·\text{trace}(A\circ A)+{\mu }_2^2·\text{trace}{(A)}^2+2{\mu }_2^2·\text{trace}(A^2),$$
   because $A_{ii}^2={(A\circ A)}_{ii}$.

3. Define k to be such that ${\mu }_4-{\mu }_2^2=2k{\mu }_2^2$, namely, k is related to measures of dispersion pertaining to X_i: $\sqrt{2k}$ is the coefficient of variation, and $(2k+1)$ is the kurtosis associated to the random variable X_i. With this, we have

   $$\mathcal{L}(W)={\mu }_2^2·\text{trace}{(A)}^2+2{\mu }_2^2\left(k{\displaystyle \sum _{i=1}^d{A}_{ii}^2}+2{\displaystyle \sum _{i<j}{A}_{ij}^2}\right).$$

From here, the desired conclusion follows because

andtogether with Equation (7).

4.2. Proof of Theorem 1

1. Note first that using Theorem 12 part (c), we have

   $$\mathcal{L}(W)\ge \min \{\text{Var}(X_i^2),2\mathbb{E}{\left[X_i^2\right]}^2\}\text{trace}(A^2).$$

   Now, fix any $W\in {\mathbb{R}}^{m\times d}$ with $\text{rank}(W)<d$. Let $a_1\ge \cdots \ge a_d$ be the eigenvalues of ${(W^{*})}^T{W}^{*}$, $b_1\ge \cdots \ge b_d$ be the eigenvalues of $-W^{T}W$, and ${\lambda }_1\ge \cdots \ge {\lambda }_d$ be the eigenvalues of ${(W^{*})}^T{W}^{*}-W^{T}W$. Because W is rank deficient, we have $b_1=0$. Furthermore, $a_d={\sigma }_{\text{min}}{(W^{*})}^2$ because the eigenvalues of ${(W^{*})}^T{W}^{*}$ are precisely the squares of the singular values of $W^{*}$. Now, recall the (Courant–Fischer) variational characterization of the eigenvalues (Horn and Johnson [47]). If M is a d × d matrix with eigenvalues $c_1\ge \cdots \ge c_d$, then

   $$c_1=\underset{x:{\Vert x\Vert }_2=1}{\max } x^{T}Mx\hspace{1em}\text{and}\hspace{1em}{c}_d=\underset{x:{\Vert x\Vert }_2=1}{\min } x^{T}Mx.$$

   With this, fix an $x\in {\mathbb{R}}^d$ with ${\Vert x\Vert }_2=1$. Then,

   $$x^T({(W^{*})}^T{W}^{*}-W^{T}W)x\ge \underset{x:{\Vert x\Vert }_2=1}{\min } x^T{(W^{*})}^T{W}^{*}x+x^T(-W^{T}W)x=a_d+x^T(-W^{T}W)x.$$

   Because this inequality holds for every x with ${\Vert x\Vert }_2=1$, we can take the max over all x and arrive at

   $${\lambda }_1=\underset{x:{\Vert x\Vert }_2=1}{\max } x^T({(W^{*})}^T{W}^{*}-W^{T}W)x\ge a_d+b_1=a_d\ge {\sigma }_{\text{min}}{(W^{*})}^2.$$

   Now, because ${\lambda }_1^2,\dots ,{\lambda }_d^2$ are precisely the eigenvalues of A², we have $\text{trace}(A^2)={\sum }_{i=1}^d{\lambda }_i^2\ge {\lambda }_1^2$. Hence, for any W with $\text{rank}(W)<d$, it holds that

   $$\mathcal{L}(W)\ge \min \{\text{Var}(X_i^2),2\mathbb{E}{\left[X_i^2\right]}^2\}{\lambda }_1^2.$$

   Finally, because ${\lambda }_1^2\ge {\sigma }_{\text{min}}{(W^{*})}^4$, the desired conclusion follows by taking the minimum over all rank-deficient W.

2. Let the eigenvalues of ${(W^{*})}^T{W}^{*}$ be denoted by ${\lambda }_1^{*},\dots ,{\lambda }_d^{*}$ with the corresponding orthogonal eigenvectors $q_1^{*},\dots ,q_d^{*}$. Namely, diagonalize ${(W^{*})}^T{W}^{*}$ as $Q^{*}{\mathrm{\Lambda }}^{*}{(Q^{*})}^T$, where the columns of $Q^{*}\in {\mathbb{R}}^{d\times d}$ are $q_1^{*},\dots ,q_d^{*}$ and ${\mathrm{\Lambda }}^{*}\in {\mathbb{R}}^{d\times d}$ is a diagonal matrix with ${({\mathrm{\Lambda }}^{*})}_{i,i}={\lambda }_i^{*}$ for every $1\le i\le d$. Let

   $$\overline{W}={\displaystyle \sum _{j=1}^{d-1}\sqrt{{\lambda }_j^{*}}}{q}_j^{*}{(q_j^{*})}^T\in {\mathbb{R}}^{d\times d}.$$

Observe that ${\overline{W}}^T\overline{W}=Q^{*}\overline{\mathrm{\Lambda }}{Q}^{*}$, where $\overline{\mathrm{\Lambda }}\in {\mathbb{R}}^{d\times d}$ is a diagonal matrix with ${(\overline{\mathrm{\Lambda }})}_{i,i}={({\mathrm{\Lambda }}^{*})}_{i,i}$ for every $1\le i\le d-1$ and ${(\overline{\mathrm{\Lambda }})}_{d,d}=0$ and that $\text{rank}(\overline{W})=d-1$. Now, let $\overline{W_1},\dots ,\overline{W_d}\in {\mathbb{R}}^d$ be the rows of $\overline{W}$ and fix a $j\in [d]$ such that $\overline{W_j}\ne 0$.

Having constructed a $\overline{W}\in {\mathbb{R}}^{d\times d}$, we now prescribe $W\in {\mathbb{R}}^{m\times d}$ as follows. For $1\le i\le d,\hspace{0.17em}i\ne j$, let $W_i=\overline{W_i}$, where W_i is the ith row of W. Then, set $W_j=\frac{1}{2}\overline{W_j}$, and for every $d+1\le i\le m$, set $W_i=\frac{\sqrt{3}}{2\sqrt{m-d}}\overline{W_j}$. For this matrix, we now claim

To see this, fix an $X\in {\mathbb{R}}^d$ and recall that $X^T{W}^{T}WX-X^T{\overline{W}}^T\overline{W}X={\Vert WX\Vert }_2^2-{\Vert \overline{W}X\Vert }_2^2$. We now compute this quantity more explicitly:

Hence, for every $X\in {\mathbb{R}}^d$, we have

Now, let $\mathrm{\Xi }=W^{T}W-{\overline{W}}^T\overline{W}$. Note that $\mathrm{\Xi }\in {\mathbb{R}}^{d\times d}$ is symmetric and $X^T\mathrm{\Xi }X=0$ for every $X\in {\mathbb{R}}^d$. Now, taking X to be e_i, that is, the ith element of the standard basis for the Euclidean space ${\mathbb{R}}^d$, we deduce ${\mathrm{\Xi }}_{i,i}=0$ for every $i\in [d]$. For the off-diagonal entries, let $X=e_i+e_j$. Then, $X^T\mathrm{\Xi }X={\mathrm{\Xi }}_{i,i}+{\mathrm{\Xi }}_{i,j}+{\mathrm{\Xi }}_{j,i}+{\mathrm{\Xi }}_{j,j}=0$, which, together with the fact that the diagonal entries of Ξ are zero, imply ${\mathrm{\Xi }}_{i,j}=-{\mathrm{\Xi }}_{j,i}$, namely, Ξ is skew-symmetric. Finally, because Ξ is also symmetric, we have ${\mathrm{\Xi }}_{i,j}={\mathrm{\Xi }}_{j,i}$, which then implies for every $i,j\in [d],\hspace{0.17em}{\mathrm{\Xi }}_{i,j}=0$, that is, Ξ = 0, and thus, $W^{T}W={\overline{W}}^T\overline{W}$.

Hence, we have for $W\in {\mathbb{R}}^{m\times d}$ with $\text{rank}(W)=d-1$,

with ${(\mathrm{\Lambda }\prime )}_{i,i}=0$ for every $1\le i\le d-1$ and ${(\mathrm{\Lambda }\prime )}_{d,d}=-{\lambda }_d^{*}$. Namely, the spectrum of the matrix $A={(W^{*})}^T{W}^{*}-W^{T}W$ contains only two values: zero with multiplicity d − 1 and ${\lambda }_d^{*}$ with multiplicity one. In particular,

Using now the upper bound provided by Theorem 12 part (c) yields the desired claim. Therefore, the energy band lower bound is tight up to a multiplicative constant.

4.3. Proof of Lemma 1

For any fixed $i\in [N],j\in [d]$, note that using sub-Gaussian property one has $\mathbb{P}(|X_i(j)|>d^{K_1})\le \exp (-C{d}^{2K_1})$; thus, $\mathbb{P}(\exists i\in [N],j\in [d]:|X_i(j)|>d^{K_1})\le Nd\exp (-C{d}^{2K_1})$, using union bound, which yields the conclusion.

4.4. Proof of Lemma 2

Let

By Lemma 1, $\mathbb{P}({\mathcal{E}}_1)\ge 1-Nd\exp (-C{d}^{2K_1})$. Now, note that

We now study $\mathbb{P}(\mathcal{E}{(A)}^c|{\mathcal{E}}_1)$; hence, assume we condition on ${\mathcal{E}}_1$ from now on. The triangle inequality yields

Observe now that

which implies (conditional on ${\mathcal{E}}_1$)

Now, the Cauchy–Schwarz inequality with respect to the inner product $〈U,V〉\triangleq \text{trace}(U^{T}V)$ yields

for every $i\in [N]$, using ${\Vert A\Vert }_F\le d^{2K_2}$.

Next, let $A^{*}={(W^{*})}^T{W}^{*}\in {\mathbb{R}}^{d\times d}$, and let ${\eta }_1^{*},\dots ,{\eta }_d^{*}$ be the eigenvalues of $A^{*}$, all nonnegative. Observe that

Now, note that ${({\eta }_1^{*})}^2,{({\eta }_2^{*})}^2,\dots ,{({\eta }_d^{*})}^2$ are the eigenvalues of ${(A^{*})}^2={(A^{*})}^T{A}^{*}$. With this reasoning, we have

Consequently, ${\Vert A^{*}\Vert }_F\le d^{2K_2}$, and therefore, the exact same reasoning yields

for every $i\in [N]$. Hence, conditional on ${\mathcal{E}}_1$, it holds that, for every $i\in [N]$,

We now apply concentration to i.i.d. sum

which is a sum of bounded random variables that are at most $4d^{4K_1+4K_2+2}$.

Now, recalling the distributional assumption on the data, we have that, conditional on ${\Vert X_i\Vert }_{\infty }\le d^{K_1}$, the data still has i.i.d. centered coordinates. In particular, the energy barrier result for the population risk as per Theorem 1 applies:

whereis controlled by the conditional moments of data coordinates.

Finally applying Hoeffding’s inequality for bounded random variables, we arrive at

with probability at least $1-\exp (-C_{3}N{d}^{-4K_1-4K_2-2})$. Namely,

Returning to (8), this yields

This completes the proof of Lemma 2.

4.5. Proof of Lemma 3

The proof is almost verbatim from Candès and Plan [14, lemma 3.1], and included herein for completeness.

Note that any $A\in {\mathbb{R}}^{d\times d},\hspace{0.17em}A⪰0$, and $\text{rank}(A)=r$ decomposes as $A=Q\mathrm{\Lambda }{Q}^T$, where $Q\in {\mathbb{R}}^{d\times r}$, satisfying $Q^{T}Q=I_d$ and $\mathrm{\Lambda }\in {\mathbb{R}}^{r\times r}$, a diagonal matrix with nonnegative diagonal entries. Notice, furthermore, that ${\Vert A\Vert }_F={\Vert \mathrm{\Lambda }\Vert }_F\le R$ as Q is orthonormal. With this, we now construct an appropriate net covering the set of all permissible Q and Σ.

Let D be the set of all r × r diagonal matrices with nonnegative diagonal entries with a Frobenius norm at most R. Let $\overline{D}$ be an $\frac{ϵ}{3}-$net for D in the Frobenius norm. Using standard results (see, e.g., Vershynin [91, lemma 5.2]), we have

Now, let $O_{d,r}=\{Q\in {\mathbb{R}}^{d\times r}:Q^{T}Q=I_d\}$. To cover $O_{d,r}$, we use a more convenient norm ${\Vert ·\Vert }_{1,2}$ defined as

where X_i is the $i\text{th}$ column of X. Define $Q_{d,r}=\{X\in {\mathbb{R}}^{d\times r}:{\Vert X\Vert }_{1,2}\le 1\}$. Note that $O_{d,r}\subset Q_{d,r}$. Furthermore, observe also that $Q_{d,r}$ has a $ϵ-$net of cardinality at most ${(3/ϵ)}^{dr}$. With this, we now take ${\overline{O}}_{d,r}$ to be a $\frac{ϵ}{3R}-$net for $O_{d,r}$. Consider now the set

Clearly,

We now claim $\overline{S_R}$ is indeed a $ϵ-$net for S_R in the Frobenius norm. To prove this, take an arbitrary $A\in S_R$, and let $A=Q\mathrm{\Lambda }{Q}^T$. There exists a $\overline{Q}\in {\overline{O}}_{d,r}$ and a $\overline{\mathrm{\Sigma }}\in \overline{D}$ such that ${\Vert \mathrm{\Sigma }-\overline{\mathrm{\Sigma }}\Vert }_F\le ϵ/3$, and ${\Vert Q-\overline{Q}\Vert }_{1,2}\le ϵ/3R$. Now, let $\overline{A}=\overline{Q}\overline{\mathrm{\Sigma }}{\overline{Q}}^T$. Observe that, using the triangle inequality,

For the first term, note that, because Q is orthonormal, ${\Vert (Q-\overline{Q})\mathrm{\Lambda }{Q}^T\Vert }_F={\Vert (Q-\overline{Q})\mathrm{\Lambda }\Vert }_F$. Next,

using ${\Vert Q-\overline{Q}\Vert }_{1,2}\le ϵ/3R$ and ${\Vert \mathrm{\Sigma }\Vert }_F\le R$. Thus, ${\Vert Q\mathrm{\Lambda }{Q}^T-\overline{Q}\mathrm{\Lambda }{Q}^T\Vert }_F\le ϵ/3$. Similarly, we also have ${\Vert \overline{Q}\overline{\mathrm{\Lambda }}{Q}^T-\overline{Q}\overline{\mathrm{\Lambda }}{\overline{Q}}^T\Vert }_F\le ϵ/3$. Finally, ${\Vert \overline{Q}\mathrm{\Lambda }{Q}^T-\overline{Q}\overline{\mathrm{\Lambda }}{Q}^T\Vert }_F={\Vert \mathrm{\Lambda }{Q}^T-\overline{\mathrm{\Lambda }}{Q}^T\Vert }_F={\Vert \mathrm{\Lambda }-\overline{\mathrm{\Lambda }}\Vert }_F\le ϵ/3$ using again the facts that Q and $\overline{Q}$ are both orthonormal. This concludes that ${\Vert \overline{A}-A\Vert }_F\le ϵ$; thus, $|\overline{S_R}|$ is indeed a $ϵ-$net for S_R, in the Frobenius norm, of cardinality at most ${(9R/ϵ)}^{dr+r}$.

As a side remark, observe that we gain an extra factor of two in the exponent owing to the fact that A is positive semidefinite (otherwise, the bound would be ${(9R/ϵ)}^{2dr+r}$).

4.6. Proof of Theorem 3

We first establish the following proposition for any W, which is a stationary point of the population risk.

Proposition 1.

Let ${\mathcal{D}}^{*}\in {\mathbb{R}}^{d\times d}$ be a diagonal matrix with ${\mathcal{D}}_{ii}^{*}={({(W^{*})}^T{W}^{*})}_{ii}$ and define $\mathcal{D}\in {\mathbb{R}}^{d\times d}$ analogously. Then, $W\in {\mathbb{R}}^{m\times d}$ enjoys the stationarity equation

$$\begin{array}{ll}\hfill & ({\mu }_4-3{\mu }_2^2)W{\mathcal{D}}^{*}+{\mu }_2^{2}W{\Vert W^{*}\Vert }_F^2+2{\mu }_2^2(W{(W^{*})}^T{W}^{*})\hfill \\ \hfill & =({\mu }_4-3{\mu }_2^2)W\mathcal{D}+{\mu }_2^{2}W{\Vert W\Vert }_F^2+2{\mu }_2^2(W(W^{T}W)).\hfill \end{array}$$

To that end, fix a $k_0\in [m]$ and ${\mathcal{\ell }}_0\in [d]$. Note that ${\nabla }_{k_0,{\mathcal{\ell }}_0}\mathcal{L}(W)=\mathbb{E}[{\nabla }_{k_0,{\mathcal{\ell }}_0}{(f(W^{*};X)-f(W;X))}^2]$, using the dominated convergence theorem. Next, $\mathbb{E}[{\nabla }_{k_0,{\mathcal{\ell }}_0}{(f(W^{*};X)-f(W;X))}^2]=0$ implies that, for every $k_0\in [m]$ and ${\mathcal{\ell }}_0\in [d]$,

Note next that ${\sum }_{j=1}^m\mathbb{E}[{〈W_j^{*},X〉}^2〈W_{k_0},X〉X_{{\mathcal{\ell }}_0}]$ computes as

We now put this object into a more convenient form. Notice that the preceding expression is

where

Observe that $B_{k_0,{\mathcal{\ell }}_0}=W_{k_0,{\mathcal{\ell }}_0}{\Vert W^{*}\Vert }_F^2$. We now study $A_{k_0,{\mathcal{\ell }}_0}$ and $C_{k_0,{\mathcal{\ell }}_0}$ more carefully. Observe that ${\sum }_{j=1}^m{(W_{j,{\mathcal{\ell }}_0}^{*})}^2={({(W^{*})}^T{W}^{*})}_{{\mathcal{\ell }}_0,{\mathcal{\ell }}_0}$. Now, let ${\mathcal{D}}^{*}\in \mathbb{R}d\times d$ be a diagonal matrix in which ${({\mathcal{D}}^{*})}_{ij}={({(W^{*})}^T{W}^{*})}_{ii}$ if i = j and zero otherwise. We then have $A_{k_0,{\mathcal{\ell }}_0}={(W{\mathcal{D}}^{*})}_{k_0,{\mathcal{\ell }}_0}$.

We now study $C_{k_0,{\mathcal{\ell }}_0}$. Recall that $W_i^{*}$ is the ith row $W^{*}$. Observe that ${\sum }_{j=1}^m{W}_{j,{\mathcal{\ell }}_0}^{*}{W}_{j,\mathcal{\ell }}^{*}={({(W^{*})}^T{W}^{*})}_{{\mathcal{\ell }}_0,\mathcal{\ell }}$. Hence,

that is, $C_{k_0,{\mathcal{\ell }}_0}={(W({(W^{*})}^T{W}^{*}))}_{k_0,{\mathcal{\ell }}_0}$. Combining everything, we have that, for every $k_0\in [m]$ and ${\mathcal{\ell }}_0\in [d]$,

In particular, stationarity yields

where the d × d diagonal matrix $\mathcal{D}$ is defined as ${\mathcal{D}}_{ii}={(W^{T}W)}_{ii}$, and entry-wise equalities are converted into equality of two matrices by varying $k_0\in [m]$ and ${\mathcal{\ell }}_0\in [d]$. □

Having now established Proposition 1 for the stationarity equation, we now study its implications for any full-rank W.

Let $W\in {\mathbb{R}}^{m\times d}$ be a stationary point with $\text{rank}(W)=d$. We first establish ${\Vert W\Vert }_F={\Vert W^{*}\Vert }_F$. Because $W\in {\mathbb{R}}^{m\times d}$ is a stationary point, it holds that, for every $(k_0,{\mathcal{\ell }}_0)\in [m]\times [d],\hspace{0.17em}{\nabla }_{k_0,{\mathcal{\ell }}_0}\mathcal{L}(W)=0$. In particular, Equation (9) holds.

Recalling now that W is full rank, it follows from the rank-nullity theorem that $\text{ker}(W)$ is trivial, that is, $\text{ker}(W)=\{0\}$. Hence, for matrices M₁, M₂ (with matching dimensions), whenever WM₁ = WM₂ holds, we deduce M₁ = M₂ because each column of $M_1-M_2$ is contained in $\text{ker}(W)$. Thus, Equation (9) then yields

Next, note that $\text{trace}({\mathcal{D}}^{*})={\sum }_{i=1}^d((W^{*}{)}^T{W}^{*}{)}_{ii}=\text{trace}({(W^{*})}^T{W}^{*})={\Vert W^{*}\Vert }_F^2$, and similarly, $\text{trace}(\mathcal{D})={\Vert W\Vert }_F^2$. In particular, taking traces of both sides in Equation (10), we get

implying that ${\Vert W^{*}\Vert }_F^2={\Vert W\Vert }_F^2$. Incorporating this into Equation (10), we then arrive at

Now, suppose $i\in [d]$. Note that inspecting the preceding (i, i) coordinate, we get

Because ${\mu }_4-{\mu }_2^2=\text{Var}(X_i^2)>0$, we then get

Now, focus on off-diagonal entries by fixing $i\ne j$. Observe that, because $\text{Var}(X_i^2)>0$, it also holds that $\mathbb{E}[X_i^2]={\mu }_2>0$. Now, note that, ${\mathcal{D}}_{ij}^{*}={\mathcal{D}}_{ij}=0$ in this case. We then have

We conclude that the matrix ${(W^{*})}^T{W}^{*}-W^{T}W$ is a zero matrix. Hence, $W=Q{W}^{*}$ for some orthonormal $Q\in {\mathbb{R}}^{m\times m}$ per Theorem 14, and $\mathcal{L}(W)=0$.

4.7. Proof of Theorem 5

Let ${\{W_t\}}_{t\ge 0}$ be a sequence of m × d matrices corresponding to the weights along the trajectory of gradient descent, that is, $W_t\in {\mathbb{R}}^{m\times d}$ is the weight matrix at iteration t of the algorithm. We first show $L<\infty$. To see this, recall Theorem 12(c): $\mathcal{L}(W)\ge {\mu }_2^2·\text{trace}{(A)}^2$, where $\text{trace}(A)={\Vert W\Vert }_F^2-{\Vert W^{*}\Vert }_F^2$. In particular, this yields ${\mu }_2^2{({\Vert W\Vert }_F^2-{\Vert W^{*}\Vert }_F^2)}^2\le \mathcal{L}(W)$. Hence, for any W with $\mathcal{L}(W)\le \mathcal{L}(W_0)$, it holds that

Namely, the (Frobenius) norm of the weights of any W with $\mathcal{L}(W)\le \mathcal{L}(W_0)$ remains uniformly bounded from above. This, in turn, yields that the (spectral norm of the) Hessian of the objective function remains uniformly bound from above for any such W because the objective is a polynomial function of W, which is precisely what we denote by L.

We now run gradient descent with a step size of $\eta <1/2L$: a second order Taylor expansion reveals that

where $\nabla \mathcal{L}(W)$ is the gradient of the population risk, evaluated at W.

In particular, $\mathcal{L}(W_1)\le \mathcal{L}(W_0)$, and furthermore, $\Vert {\nabla }^2\mathcal{L}(W_1)\Vert \le L$, where $\Vert {\nabla }^2\mathcal{L}(W)\Vert$ is the spectral norm of the Hessian matrix ${\nabla }^2\mathcal{L}(W)$. From here, we induct on k: the induction argument reveals that we can retain a step size of $\eta <1/2L$, and furthermore, we deduce that the gradient descent trajectory ${\{W_k\}}_{k\ge 0}$ is such that (i) $\mathcal{L}(W_k)\ge \mathcal{L}(W_{k+1})$ for every $k\ge 0$, and furthermore, (ii) it holds for every $k\ge 0$ that

We now establish that ${\Vert \nabla \mathcal{L}(W_k)\Vert }_2\to 0$ as $k\to \infty$. Note that the objective function is lower bounded (by zero). If the gradient is nonvanishing, then (by passing to a subsequence if necessary) each step reduces the value of the objective function at least by a certain amount, that is (uniformly) bounded away from zero. But this contradicts the fact that the objective is lower bounded. Thus, we deduce

Now, recall that the trajectory is such that $\mathcal{L}(W_k)\ge \mathcal{L}(W_{k+1})$ and ${\Vert \nabla \mathcal{L}(W_k)\Vert }_2\to 0$ as $k\to \infty$. Suppose that the initial value, $\mathcal{L}(W_0)$, is such that

In particular, for every $k\in {\mathbb{Z}}^{+}$,

Therefore, $W_k\in {\mathbb{R}}^{m\times d}$ is full rank for all k, per Theorem 1. We now establish

To see this, observe that the sequence ${\{\mathcal{L}(W_k)\}}_{k\ge 0}$ is monotonic (nonincreasing) and, furthermore, is bounded by zero from below. Hence,

exists (Rudin [76, theorem 3.14]. We now show $\mathcal{\ell }=0$.

Because the weights remain bounded along the trajectory, it follows that there exists a subsequence ${\{W_{k_n}\}}_{n\in \mathbb{N}}$ with a limit, that is, $W_{k_n}\to W^{\infty }$ as $n\to \infty$, where $W^{\infty }\in {\mathbb{R}}^{m\times d}$. Now, the continuity of $\nabla \mathcal{L}$, together with the continuity of the norm ${\Vert ·\Vert }_2$, imply that ${\Vert \nabla \mathcal{L}(W^{\infty })\Vert }_2=0$. Furthermore, continuity of $\mathcal{L}(·)$ then implies $\mathcal{L}(W^{\infty })=\mathcal{\ell }$. Now, because $W_{k_n}$s are such that $\mathcal{L}(W_{k_n})\le \mathcal{L}(W_0)$ for all $n\in \mathbb{N}$ and $\mathcal{L}(W_0)$ is strictly smaller than the rank-deficient energy barrier, by taking limits as $k\to \infty$ and using (11), we conclude that $W^{\infty }$ is full rank. Because $W^{\infty }$ is also a stationary point of the loss, by Theorem 3, we deduce $\mathcal{L}(W^{\infty })=0$, which yields $\mathcal{\ell }=0$ as desired.

4.8. Proof of Theorem 7

4.8.1. Part (a).

Let $t=\sqrt{d}$. Then, using Theorem 15, it holds that, with probability $1-2 \exp (-d/2)$,

Recall that $\sigma (A)$ denotes the spectrum of A, that is, $\sigma (A)=\{\lambda :\lambda \text{is} \text{an} \text{eigenvalue} \text{of} A\}$. We claim then the spectrum of $\gamma I-A$ is $\gamma -\sigma (A)$. To see this, simply note the following line of reasoning:

Now, let $W_0\in {\mathbb{R}}^{m\times d}$ be such that $W_0^T{W}_0=\gamma I$ with $\gamma =m+4d$. In particular, if ${\lambda }_1\le \cdots \le {\lambda }_d$ are the eigenvalues of $\gamma I-{(W^{*})}^T{W}^{*}$ with $\gamma =m+4d$; then, it holds that

Now, recall by Theorem 12(c) that

where $\sigma (W_0^T{W}_0-{(W^{*})}^T{W}^{*})=\{{\lambda }_1,\dots ,{\lambda }_d\}$. For the second term, we immediately have ${\sum }_{i=1}^d{\lambda }_i^2\le 16m{d}^2$.

For the first term, note first that, if ${\lambda }_1^{\prime }\le \cdots \le {\lambda }_d^{\prime }$ are the eigenvalues of ${(W^{*})}^T{W}^{*}$, then

where $W_{ij}^{*}\stackrel{d}{=}N(0,1)$ i.i.d. Note also that, ${(W_{ij}^{*})}^2-1$ is a centered random variable and has a subexponential tail; see Vershynin [91, lemma 5.14]. Now, letting $Z_{ij}={(W_{ij}^{*})}^2-1$ and applying the Bernstein-type inequality (Vershynin [91, proposition 5.16]), we have that, for some absolute constants $K,c>0$, it holdsfor m sufficiently large. In particular, with probability at least $1-\exp (-\mathrm{\Omega }(d))$, it, therefore, holds that

Finally, using the triangle inequality,

with probability $1-\exp (-\mathrm{\Omega }(d))$. After squaring, we obtain that ${({\sum }_{i=1}^d{\lambda }_i)}^2\le 16d^4+8d^3\sqrt{m}+d^{2}m$. In particular, we get

Using now the overparameterization $m>C{d}^2$, we further have

where

Note that, for the constant $\mathcal{C}\prime (C)$,

Next, observe that, $\sqrt{m}-2\sqrt{d}\ge \frac{1}{2}\sqrt{m}$ for m large (in the regime $m>C{d}^2$ with C large enough). Thus, using what we establish in Theorem 1, we arrive at

Finally, observe also that, if $\text{Var}(X_i^2)>0$, then $\mathbb{E}[X_i^2]>0$ as well: indeed observe that, if $\mathbb{E}[X_i^2]=0$, then X_i = 0 almost surely, for which $\text{Var}(X_i^2)=0$. In particular, $\min \{\text{Var}(X_i^2),2\mathbb{E}{[X_i^2]}^2\}>0$. Equipped with this, we then observe that provided

that is, provided C > 0 is sufficiently large, we are done.

4.8.2. Part (b).

Note that the result of Bai and Yin [3] asserts that, if $\{{\mu }_1,\dots ,{\mu }_d\}$ are the eigenvalues of

and if we define the empirical measurethen in the regime $d\to +\infty ,\hspace{0.17em}d/m\to 0$, it holds thatalmost surely, where $\omega (x)$ is the semicircle law, and moreover,namely, χ₂ is, respectively, the second moment under semicircle law, w.h.p. Now, define the same quantities as in proof of part (a), where this time $W_0^T{W}_0=m{I}_d$, and $\{{\lambda }_1,\dots ,{\lambda }_d\}=\sigma ({(W^{*})}^T{W}^{*}-m{I}_d)$. In particular, we still retain the inequality per Theorem 12(c):

Note that ${\lambda }_i=2\sqrt{md}{\mu }_i$. Hence, we obtain

w.h.p. We now control ${\sum }_{i=1}^d{\lambda }_i$ using the central limit theorem (CLT). Observe that

Now, note that

We now use CLT as $d\to \infty$ and $m/d\to \infty$. To that end, let $1/2>ϵ>0$ be fixed. Observe now that, for any arbitrary M > 0, and sufficiently large d,

In particular, using the central limit theorem, we deduce

where Z is a standard normal random variable. Now, because M > 0 is arbitrary, by sending $M\to +\infty$, we obtainand we then conclude

Hence,

with probability $1-o_d(1)$ for d sufficiently large.

Moreover,

for m large, using yet another result of Bai and Yin, see Theorem 16. From here, carrying the exact same analysis as in part (a), we obtain that, provided $m>C{d}^2$ for some large constant C > 0 and d sufficiently large, the following holds with probability $1-o_d(1)$:where W₀ is prescribed such that $W_0^T{W}_0=m{I}_d$.

4.9. Proof of Theorem 2

First, let

We start with the following claim.

Claim 1.

In the setting of Theorem 2, the following holds. With probability at least $1-\exp (-C\prime d)$ (where $C\prime >0$ is some absolute constant), it holds that, for any $W\in {\mathbb{R}}^{m\times d}$ with $\widehat{\mathcal{L}}(W)\le \frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4$,

$${\Vert W\Vert }_F\le d^{K+1},$$

provided $N\ge C^{‴}d$ for some absolute constant $C^{‴}>0$.

Proof of Claim 1.

For convenience, let ${\widehat{\mathcal{L}}}_0\triangleq \frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4$, and for the random data vector $X=(X_1,\dots ,X_d)\in {\mathbb{R}}^d$, let ${\sigma }^2=\mathbb{E}[X_1^2]$. Recall that X has i.i.d. centered coordinates with a sub-Gaussian coordinate distribution.

We have the following, in which the implication is due to Cauchy–Schwarz:

$${\widehat{\mathcal{L}}}_0\ge \frac{1}{N}{\displaystyle \sum _{1\le i\le N}(Y_i-f(}{X}_i;W){)}^2\Rightarrow {({\widehat{\mathcal{L}}}_0)}^{1/2}\ge \left|\frac{1}{N}{\displaystyle \sum _{1\le i\le N}(Y_i-f(}{X}_i;W))\right|.$$

We now establish that, with probability at least $1-2 \exp (-t^{2}d)$, the following holds provided $N\ge C{(t/ϵ)}^{2}d$: for every $W\in {\mathbb{R}}^{m\times d}$,

$$\left|\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{X}_i^T}{W}^{T}W{X}_i-{\sigma }^2{\Vert W\Vert }_F^2\right|\le ϵ{\sigma }^2{\Vert W\Vert }_F^2.$$

To see this, we begin by noticing $X_i^T{W}^{T}W{X}_i=\text{trace}(X_i^T{W}^{T}W{X}_i)=〈W^{T}W,X_i{X}_i^T〉$. Using this, we have

$$\left|\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{X}_i^T}{W}^{T}W{X}_i-{\sigma }^2{\Vert W\Vert }_F^2\right|=\left|〈W^{T}W,\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{X}_i}{X}_i^T-{\sigma }^2{I}_d〉\right|.$$

We now use Hölder’s inequality (Theorem 18) with $p=1,q=\infty ,\hspace{0.17em}U=W^{T}W$ and $V=\frac{1}{N}{\sum }_i{X}_i{X}_i^T-{\sigma }^2{I}_d$. This yields

$$\left|〈W^{T}W,\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{X}_i}{X}_i^T-{\sigma }^2{I}_d〉\right|\le {\Vert W\Vert }_F^2\Vert \frac{1}{N}{\displaystyle \sum _{1\le i\le N}{X}_i}{X}_i^T-{\sigma }^2{I}_d\Vert .$$

Observing now $\mathbb{E}[X_i{X}_i^T]={\sigma }^2{I}_d$, we have

$$\Vert \frac{1}{N}{\displaystyle \sum _{1\le i\le N}{X}_i}{X}_i^T-{\sigma }^2{I}_d\Vert \le ϵ{\sigma }^2$$

with probability at least $1-2 \exp (-t^{2}d)$ provided $N\ge C{(t/ϵ)}^{2}d$, using the concentration result on sample covariance matrix from Vershynin [91, corollary 5.50]. Hence, on this high probability event, the following holds:

$$\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{X}_i^T}(W^{*})T{W}^{*}{X}_i\le {\sigma }^2(1+ϵ){\Vert W^{*}\Vert }_F^2\hspace{1em}\text{and}\hspace{1em}\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{X}_i^T}{W}^{T}W{X}_i\ge {\sigma }^2(1-ϵ){\Vert W\Vert }_F^2.$$

Hence,

$${\widehat{\mathcal{L}}}_0\ge \frac{1}{N}{\displaystyle \sum _{1\le i\le N}(X_i^T{W}^{T}W{X}_i-X_i^T(}{W}^{*}{)}^T{W}^{*}{X}_i)\ge {\sigma }^2(1-ϵ){\Vert W\Vert }_F^2-{\sigma }^2(1+ϵ){\Vert W^{*}\Vert }_F^2.$$

This yields, for any W with $\widehat{\mathcal{L}}(W)\le {\widehat{\mathcal{L}}}_0$,

$${\Vert W\Vert }_F\le {\left(\frac{{({\widehat{\mathcal{L}}}_0)}^{1/2}}{{\sigma }^2(1-ϵ)}+\frac{1+ϵ}{1-ϵ}{\Vert W^{*}\Vert }_F^2\right)}^{1/2}$$

with probability at least $1-2 \exp (-t^{2}d)$. Now, observe that

$${\sigma }_{\text{min}}{(W^{*})}^2={\lambda }_{\text{min}}({(W^{*})}^T{W}^{*})\le \text{trace}({(W^{*})}^T{W}^{*})\le {\Vert W^{*}\Vert }_F^2\le d^{2K}.$$

Furthermore, $C_5=O(1)$. This yields

$${\widehat{\mathcal{L}}}_0=\frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4=O(d^{4K}).$$(12)

We now take $ϵ=1/2$ and conclude that

$${\Vert W\Vert }_F\le {\left(\frac{{({\widehat{\mathcal{L}}}_0)}^{1/2}}{{\sigma }^2(1-ϵ)}+\frac{1+ϵ}{1-ϵ}{\Vert W^{*}\Vert }_F^2\right)}^{1/2}\le d^{K+1}$$

for d large enough with probability at least $1-2 \exp (-t^{2}d)$, which is $1-\exp (-C\prime d)$ for some absolute constant $C\prime >0$. □

Having established Claim 1, we now return to the proof of Theorem 2. Let

A consequence of Claim 1 is that $\mathbb{P}({\mathcal{S}}_1={\mathcal{S}}_2)\ge 1-\exp (-C\prime d)$. We now establish the following.

Claim 2.

$$\mathbb{P}({\mathcal{S}}_2=Ø)\ge 1-{\left(9d^{2+4K+7}\right)}^{d^2-1}·\exp \left(-C_{3}N{d}^{-4-4K}\right)-Nd{e}^{-Cd}.$$

Note that combining Claims 1 and 2 through a union bound yields

with probability at leasttherefore establishing Theorem 2.

Proof of Claim 2.

Let $A=W^{T}W\in {\mathbb{R}}^{d\times d}$. We claim ${\Vert A\Vert }_F\le d^{2K+2}$. To see this, note that ${\Vert A\Vert }_F^2=\text{trace}(A^{T}A)=\text{trace}(A^2)$. Let ${\theta }_1,\dots ,{\theta }_d$ be the eigenvalues of A, all nonnegative as $A⪰0$, and ${\theta }_1^2,\dots ,{\theta }_d^2$ are the eigenvalues of A². With this,

$$\text{trace}(A^2)={\displaystyle \sum _{1\le i\le d}{\theta }_i^2}\le {\left({\displaystyle \sum _{1\le i\le d}{\lambda }_i}\right)}^2=\text{trace}{(A)}^2.$$

Hence, ${\Vert A\Vert }_F\le \text{trace}(A)={\Vert W\Vert }_F^2\le d^{2K+2}$ as requested.

Next, let

$$S_R=\{A\in {\mathbb{R}}^{d\times d}:\text{rank}(A)\le d-1,A⪰0,{\Vert A\Vert }_F\le R\};$$

let ${\overline{S}}_{ϵ}$ be a $ϵ-$net for $S_{d^{2K+2}}$ in the Frobenius norm, where ϵ is to be tuned appropriately later. Using Lemma 3, we have

$$|{\overline{S}}_{ϵ}|\le {\left(\frac{9d^{2K+2}}{ϵ}\right)}^{d^2-1}.$$

Now, applying Lemma 2 with $K_1=\frac{1}{2}$ and $K_2=K$ and taking a union bound across the net ${\overline{S}}_{ϵ}$, we arrive at the following conclusion:

$$\begin{array}{ll}\hfill & \mathbb{P}\left({\displaystyle \underset{A\in {\overline{S}}_{ϵ}}{\cup }\underset{\mathcal{E}{(A)}^c \text{from Lemma} 2}{\underbrace{\left\{\frac{1}{N}{\displaystyle \sum _{1\le i\le N}(}{Y}_i-X_i^{T}A{X}_i{)}^2<\frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4\right\}}}}|{\Vert X_i\Vert }_{\infty }\le \sqrt{d},1\le i\le N\right)\hfill \\ \hfill & \le {\left(\frac{9d^{2K+2}}{ϵ}\right)}^{d^2-1}\exp (-C_{3}N{d}^{-4+4K}),\hfill \end{array}$$

where

$$C_5=\min \{{\mu }_4(1/2)-{\mu }_2{(1/2)}^2,2{\mu }_2{(1/2)}^2\}\hspace{1em}\text{and}\hspace{1em}{\mu }_n(K)=\mathbb{E}[X_i^n||X_i|\le d^K].$$

Now, because $\mathbb{P}({\Vert X_i\Vert }_{\infty }<\sqrt{d},1\le i\le N)\ge 1-Nd \exp (-Cd)$ by Lemma 1, we obtain

$$\begin{array}{ll}\hfill & \mathbb{P}\left({\displaystyle \underset{A\in {\overline{S}}_{ϵ}}{\cap }\left\{\frac{1}{N}{\displaystyle \sum _{1\le i\le N}(}{Y}_i-X_i^{T}A{X}_i{)}^2\ge \frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4\right\}}\right)\hfill \\ \hfill & \ge 1-{\left(\frac{9d^{2K+2}}{ϵ}\right)}^{d^2-1}·\exp \left(-C_3\frac{N}{d^{4+4K}}\right)-Nd\exp (-Cd).\hfill \end{array}$$

In the remainder of the proof, suppose for every $A\in {\overline{S}}_{ϵ}$,

$$\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{(Y_i-X_i^{T}A{X}_i)}^2}\ge \frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4,$$

and ${\Vert X_i\Vert }_{\infty }\le d^{1/2},\hspace{0.17em}i\in [N]$, which collectively hold with probability at least

$$1-{\left(\frac{9d^{2K+2}}{ϵ}\right)}^{d^2-1}·\exp \left(-C_3\frac{N}{d^{4+4K}}\right)-2Nd\exp (-Cd).$$

Now, let $W\in {\mathbb{R}}^{m\times d}$ with ${\Vert W\Vert }_F\le d^{K+1},\hspace{0.17em}\text{rank}(W)\le d-1$. Let $A=W^{T}W$ (thus, ${\Vert A\Vert }_F\le d^{2K+2}$) and $\widehat{A}\in {\overline{S}}_{ϵ}$ be such that ${\Vert A-\widehat{A}\Vert }_F\le ϵ$. We now estimate

$$\mathrm{\Delta }\triangleq \left|\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{(Y_i-X_i^{T}A{X}_i)}^2}-\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{(Y_i-X_i^T\widehat{A}{X}_i)}^2}\right|.$$

For notational convenience, let $A^{*}={(W^{*})}^T{W}^{*}$. Now,

$$\begin{array}{ll}\mathrm{\Delta }\hfill & \le \frac{1}{N}{\displaystyle \sum _{1\le i\le N}|{(X_i^T(A-A^{*})X_i)}^2-{(X_i^T(\widehat{A}-A^{*})X_i)}^2|}\hfill \\ \hfill & =\frac{1}{N}{\displaystyle \sum _{1\le i\le N}|X_i^T(A-\widehat{A})X_i|}·|X_i^T(A+\widehat{A}-2A^{*})X_i|.\hfill \end{array}$$

Now, using Cauchy–Schwarz (for inner product $〈M,N〉\triangleq \text{trace}(M^{T}N)$),

$$|X_i^T(A-\widehat{A})X_i|=|〈A-\widehat{A},X_i{X}_i^T〉|\le {\Vert A-\widehat{A}\Vert }_F·{\Vert X_i\Vert }_2^2,$$

using ${\Vert X_i{X}_i^T\Vert }_F={\Vert X_i\Vert }_2^2$. In particular, we obtain

$$|X_i^T(A-\widehat{A})X_i|\le ϵd^2.$$

For the term $|X_i^T(A+\widehat{A}-2A^{*})X_i|$, we observe that the triangle inequality yields

$${\Vert A+\widehat{A}-2A^{*}\Vert }_F\le 4d^{2K+2}.$$

Thus,

$$|X_i^T(A+\widehat{A}-2A^{*})X_i|\le 4d^{2K+4}.$$

Using these, we obtain

$$\left|\widehat{\mathcal{L}}(W)-\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{(Y_i-X_i^T\widehat{A}{X}_i)}^2}\right|\le 4ϵd^{6+2K}=O(d^{-1})=o_d(1),$$

taking $ϵ=d^{-7-2K}$. Using, finally, the fact that

$$\frac{1}{N}{\displaystyle \sum _{1\le i\le N}{(Y_i-X_i^T\widehat{A}{X}_i)}^2}$$

is bounded away from zero across the net ${\overline{S}}_{ϵ}$, we conclude the proof of Claim 2. □

Because it is already noted that Claims 1 and 2 together yield Theorem 2, we complete the proof of Theorem 2.

4.9.1. Case of Constant d: $d=O(1)$.

We now carry out a separate analysis for the case of constant d ($d=O(1)$). We only point out the necessary modifications, hiding factors depending on the constant d under asymptotic notations.

In what follows, we use the fact that, if X is a sub-Gaussian random variable, then $\mathbb{E}[|X{|}^p]<\infty$ for every $p\ge 1$. For a proof, see Vershynin [91, lemma 5.5], which establishes a stronger conclusion that $\mathbb{E}{[|X{|}^p]}^{1/p}=O(\sqrt{p})$ for every $p\ge 1$.

4.9.2. Modifying Claim 1.

Claim 1 modifies to the following: with probability at least $1-O(1/N)$, it holds that, for any $W\in {\mathbb{R}}^{m\times d}$ with $\widehat{\mathcal{L}}(W)\le \frac{1}{2}\overline{C_5}{\sigma }_{\text{min}}{(W^{*})}^4$,

We now sketch the proof of this modified claim. For a matrix $M\in {\mathbb{R}}^{d\times d}$, denote by ${\Vert M\Vert }_{\infty }≔{\max }_{1\le i,j\le d}|M_{ij}|$ and let $ϵ>0$ be arbitrary. Then, we show that, over the randomness in $X_i\in {\mathbb{R}}^d,\hspace{0.17em}1\le i\le N$ with probability at least $1-O(1/N)$,

Indeed, fix an $ϵ>0$. Then, for any $1\le j\le d$,

This is by Chebyshev’s inequality (here, $X_i=(X_i(j):1\le j\le d)\in {\mathbb{R}}^d$). Here, we used, in particular, the fact that $\mathbb{E}[X_i{(j)}^4]<\infty$. Likewise, for any $1\le j<j\prime \le d$,

Taking a union bound over these $d(d+1)/2$ events corresponding to the entries of matrix $N^{-1}{\sum }_{1\le i\le N}{X}_i{X}_i^T$, we are done. (Note that the number of events, $d(d+1)/2$, is O(1). This, and other factors depending on ϵ are hidden under $O(·)$.) Using the trivial bound $\Vert M\Vert \le {\Vert M\Vert }_F^2$, valid for any matrix $M\in {\mathbb{R}}^{d\times d}$, we arrive at the operator norm bound

Finally, taking $ϵ=1/(2d^2)=O(1)$, we finish the proof of modified Claim 1.

4.9.3. Modifying Claim 2.

Claim 2 now modifies to $\mathbb{P}({\mathcal{S}}_2=Ø)\ge 1-O(1/N)$, and this modified version is shown as follows. Note that, for any $ϵ=O(1)$, the size of the net we consider is O(1). We claim that, with probability $1-O(1/N)$, it holds that, for any $A\in {\overline{S}}_{ϵ}$,

where

To show this, fix an $A\in {\overline{S}}_{ϵ}$. Now, instead of Lemma 2, one can apply Chebyshev’s inequality:

with probability at least $1-O(1/N)$. Here, we, in particular, used the fact $\mathbb{E}[X_i{(j)}^8]<\infty$. Becauseby Theorem 1, we establish the claim by taking a union bound over the net ${\overline{S}}_{ϵ}$, which has O(1) cardinality. The rest of the argument for Claim 2 remains (nearly) intact. In particular, the bound ${\Vert A-\widehat{A}\Vert }_F\le ϵ$ remains intact, and ${\Vert A+\widehat{A}-2A^{*}\Vert }_F$ is now O(1). Finally, keeping in mind that $\frac{1}{N}{\sum }_{1\le i\le N}{\Vert X_i\Vert }_2^4=O(1)$ with probability $1-O(1/N)$, we complete the proof by taking ϵ small enough.

Putting these together as in the proof of Theorem 2, we complete the proof.

4.10. Proof of Theorem 4

We start by computing $\nabla \widehat{\mathcal{L}}(W)$. Taking derivatives with respect to the jth row W_j of $W\in {\mathbb{R}}^{m\times d}$, we arrive at

Interpreting these gradients as a row vector and aggregating into a matrix, we then have

Assume now that $\text{rank}(W)=d$, and $\nabla \widehat{\mathcal{L}}(W)=0$. We then arrive at

We now claim that $\widehat{\mathcal{L}}(W)=0$. To see this, we take a route similar to Soltanolkotabi et al. [83, lemma 6.1]. Let $M\triangleq W^{T}W$, and consider the function

Observe that $f(·)$ is quadratic in M. Thus, for any $\widehat{M}$ with $\nabla f(\widehat{M})=0$, that is,

it is the case that $\widehat{M}$ is a global optimum of f. In particular, for any $M\in {\mathbb{R}}^{d\times d},\hspace{0.17em}f(M)\ge f(\widehat{M})$. Now, take any $\overline{W}\in {\mathbb{R}}^{m\times d}$, and observe that $\widehat{\mathcal{L}}(\overline{W})=f({\overline{W}}^T\overline{W})$. Because $\nabla f(W^{T}W)=0$, it follows that

Namely, W is indeed a global optimizer of $\widehat{\mathcal{L}}(·)$. Because $W=W^{*}$ makes the cost zero, we obtain $\widehat{\mathcal{L}}(W)=0$.

Now, using Theorem 10, we obtain that $\text{span}(X_i{X}_i^T:1\le i\le N)$ is the set of all d × d symmetric matrices with probability one provided $N\ge d(d+1)/2$. In this case, using Theorem 9, we conclude that $W^{T}W={(W^{*})}^T{W}^{*}$, concluding the proof.

4.11. Proof of Theorem 6

4.11.1. Part (a).

Note that, by Claim 1, it follows that, with probability at least $1-\exp (-C\prime d)$, it is the case that, for any W with $\widehat{\mathcal{L}}(W)\le \widehat{\mathcal{L}}(W_0)<\frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4,{\Vert W\Vert }_F\le d^{K+1}$. Now, let

thus, $\mathbb{P}({\mathcal{E}}_1)\ge 1-\exp (-C\prime d)$ andsuch that $\mathbb{P}({\mathcal{E}}_2)\ge 1-Nd \exp (-Cd)$ per Lemma 1.

Note that the $\Vert {\nabla }^2\widehat{\mathcal{L}}(W)\Vert =\text{poly}({\Vert W\Vert }_F,\Vert X_1\Vert ,\dots ,\Vert X_N\Vert )$. Thus, on the event ${\mathcal{E}}_1\cap {\mathcal{E}}_2$, which holds with probability at least $1-Nd \exp (-Cd)-\exp (-C\prime d)$, we have that

as claimed.

4.11.2. Part (b).

Suppose that the event ${\mathcal{E}}_1\cap {\mathcal{E}}_2$ (where ${\mathcal{E}}_1$ and ${\mathcal{E}}_2$ are defined, respectively, in (13) and (14)) takes place. We run the gradient descent with a step size of $\eta <1/2L$. A second order Taylor expansion reveals that

where $\nabla \widehat{\mathcal{L}}(W)$ is the gradient of the empirical risk evaluated at W. In particular, $\widehat{\mathcal{L}}(W_1)\le \widehat{\mathcal{L}}(W_0)$. Because ${\mathcal{E}}_1$ takes place, we conclude $\Vert {\nabla }^2\widehat{\mathcal{L}}(W_1)\Vert \le L=\text{poly}(d)$, where $\Vert {\nabla }^2\widehat{\mathcal{L}}(W)\Vert$ is the spectral norm of the Hessian matrix ${\nabla }^2\widehat{\mathcal{L}}(W)$. From here, we induct on k; the induction argument reveals that we can retain a step size of $\eta <1/2L$ (thus, $\eta =\text{poly}(d)$), and furthermore, along the trajectory ${\{W_k\}}_{k\ge 0}$, it holds that

Now, let T be the first time for which ${\Vert \nabla \widehat{\mathcal{L}}(W)\Vert }_F\le \zeta$, namely, the horizon required to arrive at an $\zeta -$stationary point. In what follows, we carry out our analysis in terms of ζ. At the end, we incorporate the bound (4) on ζ.

We claim $T=\text{poly}({\zeta }^{-1},d,{\sigma }_{\text{min}}{(W^{*})}^{-1})$.

To see this, note that, from the definition of T, it holds that ${\Vert \nabla \widehat{\mathcal{L}}(W_t)\Vert }_F\ge \zeta$ as $t\le T-1$. Now, a telescoping argument together with $\eta =1/\text{poly}(d)$ reveals

Using now $\widehat{\mathcal{L}}(W_T)\ge 0$, we conclude $\widehat{\mathcal{L}}(W_0)\ge T{\zeta }^2\text{poly}(d)$. Because $\widehat{\mathcal{L}}(W_0)={\widehat{\mathcal{L}}}_0$ is at most polynomial in d as per (12), we conclude $T=\text{poly}({\zeta }^{-1},d)$.

We now turn our attention to bounding its risk. Let $r_i\triangleq Y_i-X_i^T{W}^{T}W{X}_i$. Note that $\widehat{\mathcal{L}}(W)=\frac{1}{N}{\sum }_{1\le i\le N}{r}_i^2$. Now,

Using the Cauchy–Schwarz inequality, we have

Next, ${\Vert W^{T}W\Vert }_F^2=\text{trace}({(W^{T}W)}^2)\le {(\text{trace}(W^{T}W))}^2={\Vert W\Vert }_F^4$, using the fact that $W^{T}W⪰0$. In particular, on the event ${\mathcal{E}}_1$ defined as per (13), we conclude that ${\Vert W\Vert }_F\le d^{K+1}$, and therefore, ${\Vert W^{T}W\Vert }_F\le d^3$. This, together with ${\Vert W^{*}\Vert }_F\le d^K$ and the triangle inequality, then yields

with probability at least $1-\exp (-C\prime d)$. Hence, on this event,

With this, we now turn our attention to bounding

We establish that, for the event

it is the case that

This is almost a straightforward modification of the proof of the earlier energy barrier result Theorem 2, and we only point out required modifications. Take any $W\in {\mathbb{R}}^{m\times d}$ with ${\sigma }_{\text{min}}(W)<\frac{1}{2}{\sigma }_{\text{min}}(W^{*})$. In particular,

Inspecting now the proof of Theorem 1(a), we obtain that, for such a W,

and consequently, modifying Lemma 2, we have that

Using now a covering numbers bound, in the same manner as in the proof of Theorem 2, we conclude that

with probability at least

Now, suppose in the remainder of this part that the event ${\mathcal{E}}_1\cap {\mathcal{E}}_2\cap {\mathcal{E}}_3$, which is

holds true. In particular, for any W with risk less than $\frac{1}{2}{C}_5{\sigma }_{\text{min}}{(W^{*})}^4$, we have ${\sigma }_{\text{min}}(W)>\frac{1}{2}{\sigma }_{\text{min}}(W^{*})>0$ (in particular, any such W is invertible). Now, take any $\zeta -$stationary point W generated by the gradient descent. Because of the event ${\mathcal{E}}_3$ and the fact that $\widehat{\mathcal{L}}(W)<{\widehat{\mathcal{L}}}_0$, proven earlier, it holds that $\text{rank}(W)=d$, and from the definition of $\zeta -$stationarity, we have

Inspecting the proof of Theorem 4, we observe that

Thus, we arrive at

Let

Note now that

Next, we have

because of conditioning on ${\mathcal{E}}_3$ (16). Furthermore,

We now combine these findings.

We now use the bounds on $\mathbb{P}({\mathcal{E}}_1)$ as per (13), on $\mathbb{P}({\mathcal{E}}_2)$ as per (14), and on $\mathbb{P}({\mathcal{E}}_3)$ as per (17) to control $\mathbb{P}({\mathcal{E}}_1\cap {\mathcal{E}}_2\cap {\mathcal{E}}_3)$. We conclude by the union bound that, with probability at least

it holds that, for any W with ${\Vert \nabla \widehat{\mathcal{L}}(W)\Vert }_F\le \zeta$, its empirical risk is controlled as per (15):

Finally, because

per (4), we deduce $\widehat{\mathcal{L}}(W)\le ϵ$ as claimed. The running time is polynomial in ${\zeta }^{-1}$ and d, and therefore, is polynomial in ${ϵ}^{-1},\hspace{0.17em}{\sigma }_{\text{min}}{(W^{*})}^{-1}$ and d. This completes the proof of Part (b).

4.11.3. Part (c).

Let $W\in {\mathbb{R}}^{m\times d}$ be such that $\widehat{\mathcal{L}}(W)\le \kappa$. Define the matrix

We bound ${\Vert M\Vert }_F$, which ensures weights W^TW are uniformly close to ground truth weights defined as ${(W^{*})}^T{W}^{*}$. We start by conditioning: assume in the remainder that the event ${\mathcal{E}}_2$ in (14) stating ${\Vert X_i\Vert }_{\infty }\le d^{1/2}$ for every $i\in [N]$ is true; this holds with probability at least $1-Nd \exp (-Cd)$ as per Lemma 1.

Note that

To this end, consider a matrix $\mathrm{\Xi }\in {\mathbb{R}}^{N\times d(d+1)/2}$, consisting of i.i.d. rows in which the $i\text{th}$ row of Ξ is ${\mathcal{R}}_i\triangleq (X_i{(1)}^2,\dots ,X_i{(d)}^2,X_i(k)X_i(\mathcal{\ell }):1\le k<\mathcal{\ell }\le d)\in {\mathbb{R}}^{d(d+1)/2}$. Next, let

where ${\mathcal{R}}_i$ is the $i\text{th}$ row of matrix Ξ. Furthermore, let $\mathcal{M}\in {\mathbb{R}}^{d(d+1)/2}$ be a vector consisting of entries $M_{11},\dots ,M_{dd}$ and $2M_{ij},\hspace{0.17em}1\le i<j\le d$. With this notation, if $v=\mathrm{\Xi }\mathcal{M}\in {\mathbb{R}}^{N\times 1}$, then we havebecause $\widehat{\mathcal{L}}(W)\le \kappa$ by assumption.

Next, we have

We start with the second term. Recall that ${\Vert v\Vert }_2\le \sqrt{N\kappa }$, and we condition on ${\Vert X_i\Vert }_{\infty }<d^{1/2},\hspace{0.17em}1\le i\le N$. Next, using the Cauchy–Schwarz inequality,

Hence,

We now control ${\Vert {({\mathrm{\Xi }}^T\mathrm{\Xi })}^{-1}\Vert }_2^2$. This is done in a manner similar to the proof of Emschwiller et al. [33, theorem 3.2]. The main tool is the result Theorem 17 for concentration of the spectrum of random matrices with i.i.d. nonisotropic rows. The parameter setting we operate under is provided as follows.

Table

Start by verifying that, because we condition on ${\Vert X_i\Vert }_{\infty }<d^{1/2}$, it is indeed the case that the ${\mathcal{\ell }}_2-$norm of each row of Ξ is at most d; thus, the preceding value of m works.

We now claim $\gamma ={\Vert \mathrm{\Sigma }\Vert }^{1/2}\delta$. To prove this, it suffices to show

Using Emschwiller et al. [33, theorem 5.1] (also see Remark 2) with k = 2, we obtain ${\sigma }_{\text{min}}(\mathrm{\Sigma })\ge c{d}^{-4}$ for some absolute constant c > 0 depending only on the data coordinate distribution. Consequently,

which is below sample size N as requested. Therefore, $\gamma ={\Vert \mathrm{\Sigma }\Vert }^{1/2}\delta$.

We now claim

This is equivalent to establishing

Using again Emschwiller et al. [33, theorem 5.1], we have $\Vert \mathrm{\Sigma }\Vert <f{d}^4$ for some absolute constant f > 0. This yields

for some absolute constant $C\prime >0$, which again holds for our case as $N>d^{18+\frac{4}{3}}$.

The rest is verbatim from Emschwiller et al. [33]. We now apply Theorem 17. With probability at least $1-d^2 \exp (-c{N}^{1/4})$ (here, c > 0 is an absolute constant), it holds that

Now, for $D=d(d+1)/2$,

which implies, for every v on the sphere ${\mathbb{S}}^{D-1}=\{v\in {\mathbb{S}}^D:{\Vert v\Vert }_2=1\}$,

Now, using the Courant–Fischer variational characterization of the smallest singular value (Horn and Johnson [47]), we obtain

with probability at least $1-\exp (-c\prime N^{1/4})$, where $c\prime >0$ is a positive absolute constant smaller than c.

We now return to (19) to specifically bound $\Vert {({\mathrm{\Xi }}^T\mathrm{\Xi })}^{-1}\Vert$. Let A be any matrix A. Note that $\Vert A^{-1}\Vert ={\sigma }_{\text{min}}{(A)}^{-1}$. Indeed, taking the singular value decomposition $A=U\mathrm{\Sigma }{V}^T$ and observing $A^{-1}={(V^T)}^{-1}{\mathrm{\Sigma }}^{-1}{U}^{-1}$, we obtain $\Vert A^{-1}\Vert ={\max }_i{({\sigma }_i(A))}^{-1}={\sigma }_{\text{min}}{(A)}^{-1}$. This, together with (23), yields

with probability at least $1-\exp (-c\prime N^{1/4})$.

We now have all ingredients to execute the bound in (19). Combining Equations (21) and (24), we get

for some constant C > 0. Using (18) from Part (b), we have that κ can be takenwith probability at least

Because ${\Vert \mathcal{M}\Vert }_2^2\le 4C\kappa d^{11}$ with probability at least $1-\exp (-c\prime N^{1/4})$, we have that

with probability at leastby the union bound. As ${\Vert M\Vert }_F\le {\Vert \mathcal{M}\Vert }_2$ andper (4), we arrive at ${\Vert W^{T}W-{(W^{*})}^T{W}^{*}\Vert }_F\le ϵ$ as claimed.

We now show the generalization ability. For any $W\in {\mathbb{R}}^{m\times d}$, using auxiliary result Theorem 12(c), we have

where $M=W^{T}W-{(W^{*})}^T{W}^{*}\in {\mathbb{R}}^{d\times d}$. Now, note that $\text{trace}{(M)}^2=|{\sum }_{1\le i\le d}{M}_{ii}{|}^2\le d{\sum }_{1\le i\le d}{M}_{ii}^2\le d{\Vert M\Vert }_F^2$ by Cauchy–Schwarz. Furthermore, $\text{trace}(M^2)=\text{trace}(M^{T}M)={\Vert M\Vert }_F^2$. Thus,for d large. Because ${\Vert M\Vert }_F^2\le {\Vert \mathcal{M}\Vert }_2^2\le {(C\prime )}^2\zeta d^{15+4K}{\sigma }_{\text{min}}{(W^{*})}^{-2}$, we obtain

Finally, because

per (4), we conclude the proof of generalization bound, that is, $\mathcal{L}(W)\le ϵ$.

Remark 2.

The argument presented uses Emschwiller et al. [33, theorem 5.1]. Even though that result is stated for distributions supported on ${[-1,1]}^d$, it still applies under the weaker assumption that the distribution has finite moments of all orders; see Emschwiller et al. [33, remark 5.5].

4.11.4. Case of Constant d: $d=O(1)$.

We provide a very brief sketch for the argument in the case $d=O(1)$. The argument is quite similar to the one in Theorem 2. Similar to the analysis (of $d=O(1)$ case) conducted for Theorem 2, we use the fact that, if X has a sub-Gaussian random variable, then $\mathbb{E}{[|X{|}^p]}^{1/p}=O(\sqrt{p})$ for every $p\ge 1$, and in particular, $\mathbb{E}[|X{|}^p]<\infty$ for all $p\ge 1$; see Vershynin [91, lemma 5.5] for a more precise statement.

Next, the upper bound on the energy value now modifies to $\frac{1}{2}\overline{C_5}{\sigma }_{\text{min}}{(W^{*})}^4$.

4.11.5. Part (a).

Note that part (a) for the case of general d follows from earlier Claim 1. For the case when d is constant, part (a) now follows from modified Claim 1, provided under Theorem 2 for the case $d=O(1)$. That is, for the event

it is the case that $\mathbb{P}({\mathcal{E}}_1)\ge 1-O(1/N)$, where $\overline{C_5}$ is the constant appearing in Theorem 2.

Furthermore,

for some absolute constant D > 0, and for any constant D > 0,with probability at least $1-O(1/N)$ (where we use, in particular, the fact $\mathbb{E}[X_i{(j)}^{2D}]<\infty$).

Combining these, we find that

with probability at least $1-O(1/N)$.

4.11.6. Part (b).

The analysis for time horizon T remains intact. Furthermore, the entire analysis leading to (15) remains (nearly) intact, and this equation now modifies to

because the Frobenius norm terms involved (all of which are polynomials in d) are now O(1). The event ${\mathcal{E}}_3$ appearing in (16) modifies now towhich holds with probability at least $1-O(1/N)$ (the modifications are exactly the same as those noted in Theorem 2 for the case $d=O(1)$). The rest of the analysis in Part (b) is exactly the same: combining modified versions of events ${\mathcal{E}}_1$ and ${\mathcal{E}}_3$ (note that there is no need to incorporate the event ${\mathcal{E}}_2$, which for the case of general d, is required for truncation) via a union bound and recalling Equation (4) on ζ, and it follows that, with probability at least $1-O(1/N),\hspace{0.17em}\widehat{\mathcal{L}}(W)\le ϵ$.

4.11.7. Part (c).

The modification for this part is as follows. First, we do not condition on ${\mathcal{E}}_2$ as earlier. Instead, we apply Chebyshev’s inequality (elaborated subsequently). The entire analysis leading up to (20) remains the same. Note now that ${\mathrm{\Xi }}^{T}v\in {\mathbb{R}}^{d(d+1)/2}$. For each coordinate ${({\mathrm{\Xi }}^{T}v)}_i$ of this vector, we have, using Chebyshev’s inequality,

with probability $1-O(1/N)$. Taking a union bound over $d(d+1)/2=O(1)$ coordinates yields that, with probability $1-O(1/N)$, this remains true over all $1\le i\le d(d+1)/2$.

Next, to control ${\Vert |{({\mathrm{\Xi }}^T\mathrm{\Xi })}^{-1}\Vert }_2^2$, we do not need a delicate concentration result (such as Theorem 17) as earlier. Instead, we take the following route.

Fix $ϵ>0$ to be tuned. Recall the notation ${\mathcal{R}}_i$ from earlier, where ${\mathcal{R}}_i$ is the $i\text{th}$ row of matrix $\mathrm{\Xi }\in {\mathbb{R}}^{N\times d(d+1)/2}$ and recall that ${\mathcal{R}}_i,\hspace{0.17em}1\le i\le N$ are i.i.d. random vectors. Using the outer product representation of matrix multiplication as before, we have

Consequently,

where $\mathbb{E}[·]$ acts entry-wise.

Because $d=O(1)$, a simple application of Chebyshev’s inequality together with a union bound over $\mathrm{\Theta }(d^4)$ entries (of $N^{-1}{\mathrm{\Xi }}^T\mathrm{\Xi }$) yields

with probability at least $1-O(1/N)$. Using now $\Vert M\Vert \le {\Vert M\Vert }_F^2$ valid for any matrix M, we obtainwith probability $1-O(1/N)$. Similar to earlier, ${\sigma }_{\text{min}}(\mathrm{\Sigma })=\mathrm{\Omega }(1)$. Furthermore, the analysis starting from (22) and leading to (23) remains intact (with γ replaced with ${ϵ}^2{d}^4,\hspace{0.17em}ϵ>0$ to be tuned). In particular, for ϵ sufficiently small, it is the case that, with probability at least $1-O(1/N)$,

The rest of the analysis remains intact except that the probability bounds are now modified to $1-O(1/N)$. Finally, recalling the bound (4) on ζ, we find that, with probability $1-O(1/N)$,

4.12. Proof of Theorem 8

Let $W_0^T{W}_0=m{I}_d$, and let $\{{\lambda }_1,\dots ,{\lambda }_d\}=\sigma ({(W^{*})}^T{W}^{*}-m{I}_d)$. In what follows, recall the quantities from the proof of Theorem 7(b): ${\sigma }_{*}\triangleq \text{Var}({(W_{ij}^{*})}^2-1),\hspace{0.17em}{\chi }_2\triangleq \int x^2\hspace{0.17em}d\omega (x)$, where $\omega (x)$ is the semicircle law. Fix now an arbitrary $ϵ>0$ and a K > 0.

We start by defining several auxiliary events:

Note that from the proof of Theorem 7(b) that we have $\mathbb{P}({\mathcal{E}}_i)\ge 1-o_d(1)$ for i = 1, 2, 3, and from the union bound and sub-Gaussianity of X, $\mathbb{P}({\mathcal{E}}_4)\ge 1-N \exp (-Cd)$. Thus,

In what follows, suppose we condition on the event ${\cap }_{1\le i\le 4}{\mathcal{E}}_i$. Note that, in this conditional universe, it is still the case that X_i, $1\le i\le N$ are i.i.d. random vectors with centered i.i.d. coordinates. Using now Hölder’s inequality (Theorem 18) with $p=1,q=\infty ,\hspace{0.17em}U=X_i{X}_i^T$, and $V={(W^{*})}^T{W}^{*}-m{I}_d$, we arrive at

where we use the fact that $\text{trace}(X_i{X}_i^T)={\Vert X_i\Vert }_2^2\le d^2$ (recall the conditioning on ${\mathcal{E}}_4$). Using Hoeffding’s inequality, we havewith probability at leastwhere

Namely, $\mathcal{L}(W_0)$ is the population risk in the conditional universe.

Next, in this conditional space, using Theorem 12(c), we arrive at

Finally, carrying out the same analysis as in the end of the proof of Theorem 7, we deduce

provided $m>C^{″}{d}^2$ for a large enough constant $C^{″}$, namely, provided that the network is sufficiently overparameterized.

4.13. Proof of Theorem 9

1. Let $\text{span}(X_i{X}_i^T:i\in [N])=\mathcal{S}$, the set of all d × d symmetric matrices, and let $M\in \mathcal{S}$ be such that for any i, $X_i^{T}M{X}_i=0$. We establish M = 0. Let $1\le k,\mathcal{\ell }\le d$ be two fixed indices. To that end, let ${\theta }_i^{(k,\mathcal{\ell })}\in \mathbb{R}$ be such that ${\sum }_{i=1}^N{\theta }_i^{(k,\mathcal{\ell })}{X}_i{X}_i^T=e_k{e}_{\mathcal{\ell }}^T+e_{\mathcal{\ell }}{e}_k^T$, where the column vectors $e_k,e_{\mathcal{\ell }}\in {\mathbb{R}}^d$ are, respectively, the kth and $\mathcal{\ell }th$ elements of the standard basis for ${\mathbb{R}}^d$. Such ${\theta }_i^{(k,\mathcal{\ell })}$ indeed exist because of the spanning property. Observe that $2M_{k,\mathcal{\ell }}=e_k^{T}M{e}_{\mathcal{\ell }}+e_{\mathcal{\ell }}^{T}M{e}_k=\text{tr}(e_k^{T}M{e}_{\mathcal{\ell }}+e_{\mathcal{\ell }}^{T}M{e}_k)$. Now, using the fact that $\text{tr}(\mathit{\text{ABC}})=\text{tr}(\mathit{\text{BCA}})=\text{tr}(\mathit{\text{CAB}})$ for all matrices A, B, C (with matching dimensions), we have

   $$2M_{k,\mathcal{\ell }}=\text{tr}(M{e}_{\mathcal{\ell }}{e}_k^T+M{e}_k{e}_{\mathcal{\ell }}^T)=\text{tr}\left({\displaystyle \sum _{i=1}^N{\theta }_i^{(k,\mathcal{\ell })}}M{X}_i{X}_i^T\right)={\displaystyle \sum _{i=1}^N{\theta }_i^{(k,\mathcal{\ell })}}\text{tr}(X_i^{T}M{X}_i)=0,$$
   for every $k,\mathcal{\ell }\in [d]$. Finally, if W is such that $\widehat{\mathcal{L}}(W)=0$, then $X_i^{T}M{X}_i=0$ for any i, where $M={(W^{*})}^T{W}^{*}-W^{T}W$. Hence, provided that the geometric condition holds, we have M = 0, that is, $W^{T}W={(W^{*})}^T{W}^{*}$. From here, the final conclusion follows per Theorem 14. Because $W^{T}W={(W^{*})}^T{W}^{*}$, W clearly has zero generalization error, that is, $\mathcal{L}(W)=0$.

2. Our goal is to construct a $W\in {\mathbb{R}}^{m\times d}$ with $f(W^{*};X_i)=f(W;X_i)$ for every $i\in [N]$, whereas $W^{T}W\ne {(W^{*})}^T{W}^{*}$. Consider the inner product $〈A,B〉=\text{trace}(AB)$ in the space of all symmetric d × d matrices. Find $0\ne M\in {\mathbb{R}}^{d\times d}$, a symmetric matrix, such that $M\in {\text{span}}^{\perp }(X_i{X}_i^T:i\in [N])$, that is, $X_i^{T}M{X}_i=0$ for every $i\in [N]$. We can find such M satisfying ${\Vert M\Vert }_2=1$. Consider the linear matrix function $M(\delta )={(W^{*})}^T{W}^{*}+\delta M$. Note that $M(\delta )$ is symmetric for every δ. We claim that, under the hypothesis of the theorem, there exists a ${\delta }_0>0$ such that $M(\delta )$ is positive semidefinite for every $\delta \in [0,{\delta }_0]$ and that there exists $W_{\delta }\in {\mathbb{R}}^{m\times d}$ with $W_{\delta }^T{W}_{\delta }=M(\delta )$ for all $\delta \in [0,{\delta }_0]$. Observe that, because $\text{rank}(W^{*})=d$, then ${(W^{*})}^T{W}^{*}\in {\mathbb{R}}^{d\times d}$ with $\text{rank}({(W^{*})}^T{W}^{*})=d$. Therefore, the eigenvalues ${\lambda }_1^{*},\dots ,{\lambda }_d^{*}$ of ${(W^{*})}^T{W}^{*}$ are all positive. In particular $\{{\lambda }_i^{*}:i\in [d]\}\subset [{\delta }_1,\infty )$ with ${\delta }_1={\sigma }_{\text{min}}{(W^{*})}^2$. Now, let ${\mu }_1(\delta ),\dots ,{\mu }_d(\delta )$ be the eigenvalues of $M(\delta )$. Using Weyl’s inequality (Horn and Johnson [47]), we have $|{\mu }_i(\delta )-{\lambda }_i^{*}|\le \delta {\Vert M\Vert }_2=\delta$ for every i. In particular, taking $\delta \le {\delta }_1$, we deduce, for every $i\in [d]$, it holds that ${\mu }_i(\delta )\ge {\lambda }_i^{*}-{\delta }_1\ge 0$, that is, $\{{\mu }_i(\delta ):i\in [d]\}\subset [0,\infty )$. In particular, we also have that $M(\delta )$ is symmetric, and thus, it is positive semidefinite. Thus, there exists a $\overline{W_{\delta }}\in {\mathbb{R}}^{d\times d}$ such that ${\overline{W_{\delta }}}^T\overline{W_{\delta }}=M(\delta )$. Now, using the same idea as in the proof of Theorem 1(c), we then deduce that, for any $\widehat{m}\ge d$, there exists a matrix $W_{\delta }\in {\mathbb{R}}^{\widehat{m}\times d}$ such that $W_{\delta }^T{W}_{\delta }={\overline{W_{\delta }}}^T\overline{W_{\delta }}=M(\delta )$. In particular, for this $W_{\delta }$, if $f(W_{\delta },X)$ is the function computed by the neural network with weight matrix $W_{\delta }\in {\mathbb{R}}^{\widehat{m}\times d}$, then on the training data, $(X_i:i\in [N]),\hspace{0.17em}f(W_{\delta };X_i)=X_i^T{W}_{\delta }^T{W}_{\delta }{X}_i=X_i^T{(W^{*})}^T{W}^{*}{X}_i=f(W^{*};X_i)$ because $X_i^{T}M{X}_i=0$ for all $i\in [N]$. At the same time, $W_{\delta }^T{W}_{\delta }-{(W^{*})}^T{W}^{*}=\delta M\ne 0$ because $\delta \ne 0$ and $M\ne 0$, and therefore, $W_{\delta }^T{W}_{\delta }\ne {(W^{*})}^T{W}^{*}$.

Finally, to show $\mathcal{L}(W_{\delta })>0$, we argue as follows. Suppose $\mathcal{L}(W_{\delta })=0$. Then, by Theorem 13, it follows that $\psi (X)=X^{T}AX=0$ identically, where $A=W_{\delta }^T{W}_{\delta }-{(W^{*})}^T{W}^{*}$. Now, letting ${\xi }_1,\dots ,{\xi }_d$ be the eigenvectors of A (with corresponding eigenvalues ${\lambda }_1,\dots ,{\lambda }_d$), we obtain ${\xi }_i^{T}A{\xi }_i={\lambda }_i{\xi }_i^T{\xi }_i={\lambda }_i{\Vert {\xi }_i\Vert }_2^2=0$. We, namely, obtain ${\lambda }_i=0$ for every $i\in [d]$. Finally, because A is symmetric and, hence, admits a diagonalization of form $A=\mathcal{Q}\mathrm{\Lambda }\mathcal{Q}$ with diagonal entries of Λ being zero, we deduce A is identically zero, which contradicts with the fact that $A=\delta M$, which is a nonzero matrix.

4.14. Proof of Theorem 10

Recall that $\mathcal{S}=\{M\in {\mathbb{R}}^{d\times d}:M^T=M\}$. Note that this space has dimension $\left(\begin{array}{c}d\\ 2\end{array}\right)+d$. For any $1\le k\le \mathcal{\ell }\le d$, it is easy to see that the matrices $e_k{e}_{\mathcal{\ell }}^T+e_{\mathcal{\ell }}{e}_k^T$ are linearly independent, and there are precisely $\left(\begin{array}{c}d\\ 2\end{array}\right)+d$ such matrices. With this in mind, the statement of part (b) is immediate.

We now prove part (a) of the theorem. For any X_i, let $X_i(j)$ be the jth coordinate of X_i with $j\in [d]$, and let ${\mathcal{Y}}_i$ be a $d(d+1)/2-$dimensional vector obtained by retaining $X_i{(1)}^2,\dots ,X_i{(d)}^2$ and the products $X_i(k)X_i(\mathcal{\ell })$ with $1\le k<\mathcal{\ell }\le d$. Now, let $\mathcal{X}$ be an $n\times d(d+1)/2$ matrix, whose rows are ${\mathcal{Y}}_1,\dots ,{\mathcal{Y}}_n$. Our goal is to establish

when $n=d(d+1)/2$, where the probability is taken with respect to the randomness in $X_1,\dots ,X_n$ (in particular, this yields, for $n\ge d(d+1)/2,\hspace{0.17em}\mathbb{P}(\text{rank}(\mathcal{X})=d(d+1)/2)$ almost surely). Now, recalling Theorem 13, it then suffices to show that $\text{det}(\mathcal{X})$ is not identically zero when viewed as a polynomial in $X_i(j)$ with $i\in [N],\hspace{0.17em}j\in [d]$.

We now prove part (b) by providing a deterministic construction (of the matrix $\mathcal{X})$ under which $\text{det}(\mathcal{X})\ne 0$. Let $p_1<\cdots <p_d$ be distinct prime numbers. For every $1\le t\le N$, set

In particular, $X_1={(1,1,\dots ,1)}^T\in {\mathbb{R}}^d$, which then implies that ${\mathcal{Y}}_1$ is a vector of all ones. Now, we study ${\mathcal{Y}}_2$. The entries of ${\mathcal{Y}}_2$, called $z_1,\dots ,z_{d(d+1)/2}$, are of form $p_i^2$ with $i\in [d]$ or $p_i{p}_j$, where $1\le i<j\le d$. By the fundamental theorem of arithmetic, we have $p_i{p}_j=p_k{p}_{\mathcal{\ell }}\Rightarrow \{p_i,p_j\}=\{p_k,p_{\mathcal{\ell }}\}$, and therefore, $z_1,\dots ,z_{d(d+1)/2}$ are pairwise distinct. With this construction, the matrix $\mathcal{X}$ is a Vandermonde matrix with determinant

Because $z_k\ne z_{\mathcal{\ell }}$ for every $k\ne \mathcal{\ell }$ (from the construction on ${\mathcal{Y}}_2$, which, in turn, is constructed from X₂), this determinant is nonzero, proving the claim.

4.14. Proof of Theorem 11

1. Note that, if $N\ge N^{*}$, then, combining parts (a) of Theorems 9 and 10, we have that, with probability one, $\text{span}(X_i{X}_i^T:i\in [N])=\mathcal{S}$, which, together with $\widehat{\mathcal{L}}(W)=0$, imply that

   $$\mathbb{P}(E\ne Ø)=0,$$
   where $E=\{W\in {\mathbb{R}}^{m\times d}:W^{T}W\ne {(W^{*})}^T{W}^{*};\widehat{\mathcal{L}}(W)=0\}$ from which the desired conclusion follows.

2. Assume W is taken as in proof of Theorem 9(b), that is,

   $$A={(W^{*})}^T{W}^{*}-W^{T}W=\delta M\hspace{1em}\text{where}\hspace{1em}\delta ={\sigma }_{\text{min}}{(W^{*})}^2\hspace{1em}\text{and}\hspace{1em}\Vert M\Vert =1,$$
   with $M^T=M$. Let $\{{\lambda }_1,\dots ,{\lambda }_d\}$ be the spectrum of the matrix δM. Using now Theorem 12(c), we have the lower bound
   $$\begin{array}{ll}\mathcal{L}(W)\hfill & \ge \mathbb{E}{[X_i{(j)}^2]}^2\text{trace}{(A)}^2+\min \{\text{Var}(X_i{(j)}^2),2\mathbb{E}{[X_i{(j)}^2]}^2\}·\text{trace}(A^2)\hfill \\ \hfill & \ge \min \{\text{Var}(X_i{(j)}^2),2\mathbb{E}{[X_i{(j)}^2]}^2\}\left({\displaystyle \sum _{i=1}^d{\lambda }_i^2}\right)\hfill \\ \hfill & \ge \min \{\text{Var}(X_i{(j)}^2),2\mathbb{E}{[X_i{(j)}^2]}^2\}{\lambda }_{\text{max}}{(\delta M)}^2,\hfill \end{array}$$
   because $\text{trace}(A^2)={\sum }_{i=1}^d{\lambda }_i^2$. Finally, because ${\lambda }_{\text{max}}{(\delta M)}^2={\delta }^2={\sigma }_{\text{min}}{(W^{*})}^4$ (as the spectral norm of M is one), we arrive at the desired conclusion.